New sort algorithm, upgraded

A while ago, I wrote a new sort algorithm.

If you haven't read it, please check it out before reading. New sort algorithm?

Read it? OK. Let's go.

Review of the original algorithm

Today, I upgraded it.

The original algorithm is a bit slow, a lot of pop , insert operations, so I tried to speed it up.

The original algorithm is like this (I added copy of the input list to avoid modifying it, and debug flag to activate printing, but it's not important for the algorithm itself.):

def sort(arr: list, debug=False):
    iterables_list = [copy.copy(arr),]
    while len(iterables_list[-1]) > 1:
        iterables_list.append([])
        if debug:
            print("a", iterables_list)
        i = 0
        while i < len(iterables_list[-2])-1:
            if iterables_list[-2][i] > iterables_list[-2][i+1]:
                iterables_list[-1].append(iterables_list[-2][i+1])
                iterables_list[-2].pop(i+1)
                if debug:
                    print("b", iterables_list)
            else:
                i += 1
        if debug:
            print("c", iterables_list)

    if len(iterables_list[-1]) == 0:
        iterables_list.pop()

    while len(iterables_list) > 1:
        i = 0
        while len(iterables_list[-1]) > 0:
            if iterables_list[-1][0] < iterables_list[-2][i]:
                iterables_list[-2].insert(i, iterables_list[-1][0])
                iterables_list[-1].pop(0)
                if debug:
                    print("d", iterables_list)
            else:
                i += 1
        iterables_list.pop()
        if debug:
            print("e", iterables_list)
    return iterables_list[0]

While this algorithm uses pop and insert a lot, I tried to avoid them in the upgraded version.

Upgraded version

The upgraded version is this:

def new_sort(arr: list, debug=False):
    iterable = copy.copy(arr)
    layer = [0 for _ in range(len(iterable))]
    layer_count = [len(iterable)]

    while layer_count[-1] > 1:
        current_layer_index = len(layer_count) - 1
        layer_count.append(0)
        if debug:
            print("a", layer, layer_count)
        i = 0
        while i < len(iterable) and layer[i] != current_layer_index:
            i += 1
        j = i + 1
        while j < len(iterable):
            if layer[j] == current_layer_index:
                if iterable[i] > iterable[j]:
                    layer[j] += 1
                    layer_count[current_layer_index + 1] += 1
                    layer_count[current_layer_index] -= 1
                    if debug:
                        print("b", layer, layer_count)
                else:
                    i = j
            j += 1
            if debug:
                print("c", layer, layer_count)

    if layer_count[-1] == 0:
        layer_count.pop()

    result = []
    while len(layer_count) > 1:
        i = 0
        j = 0
        result = []
        new_layer = []

        while layer_count[-1] > 0:
            while not layer[i] == len(layer_count) - 1:
                i += 1
            while not layer[j] == len(layer_count) - 2:
                j += 1
            if layer[i] == len(layer_count) - 1 and layer[j] == len(layer_count) - 2:

                if iterable[i] < iterable[j]:
                    result.append(iterable[i])
                    new_layer.append(layer[i] - 1)
                    layer_count[-1] -= 1
                    layer_count[-2] += 1
                    if debug:
                        print("d", new_layer, layer_count, result)
                    i += 1
                else:
                    result.append(iterable[j])
                    new_layer.append(layer[j])
                    if debug:
                        print("d", new_layer, layer_count, result)
                    j += 1

        while j < len(iterable):
            if layer[j] == len(layer_count) - 2:
                result.append(iterable[j])
                new_layer.append(layer[j])
                if debug:
                    print("d", new_layer, layer_count, result)
            j += 1

        for i in range(len(layer)):
            if layer[i] < len(layer_count) - 2:
                result.append(iterable[i])
                new_layer.append(layer[i])
        if debug:
            print("e", new_layer, layer_count, result)
        iterable = result
        layer = new_layer
        layer_count.pop()
    return result

The main idea is to virtually split the list into layers with layer list, and increment/decrement layer indices instead of popping and inserting them.

This way, we can avoid the overhead of pop and insert , and the algorithm should be faster.

Instead of this, the code became more complex and longer, but I think it's worth it.

Benchmark

I benchmarked the original and upgraded versions with random lists of different sizes.

def benchmark(sort_func, n=200, trials=10):
    times = []
    for _ in range(trials):
        target = [random.randint(0, 1000) for _ in range(n)]

        start = time.perf_counter()
        sort_func(target.copy())
        end = time.perf_counter()

        times.append(end - start)

    avg = statistics.mean(times)
    stdev = statistics.stdev(times) if len(times) > 1 else 0
    return avg, stdev


if __name__ == "__main__":
    N_SIZE = 30000
    TRIALS = 10

    print(f"--- Start Benchmark (Size:{N_SIZE}, Trials:{TRIALS}) ---")

    avg1, dev1 = benchmark(sort, N_SIZE, TRIALS)
    print(f"Old Version: Average {avg1:.5f}s (±{dev1:.5f})")

    avg2, dev2 = benchmark(new_sort, N_SIZE, TRIALS)
    print(f"Upgraded Version: Average {avg2:.5f}s (±{dev2:.5f})")

    improvement = (avg1 / avg2) if avg2 > 0 else 0
    print(f"\nResult: The upgraded version is approximately {improvement:.1f} times faster than the old version.")

The results are below.

As you can see, the upgraded version is faster and more consistent than the old version, especially as the size of the list increases.

The improvement is significant, especially for larger lists, where the upgraded version is approximately 3.5 times faster than the old version.

Conclusion

In this article, I upgraded a new sort algorithm that I wrote a while ago.

The upgraded version is faster and more consistent than the old version, especially as the size of the list increases.

The main idea is still the same, compare and drop layers because this idea is what makes this algorithm (maybe) unique.

I hope you enjoyed this article, and if you have any questions or suggestions, please let me know through form or twitter.

print("see you next time!")