5
\$\begingroup\$

I have made a sorting algorithm in Python 3. This sorting algorithm is a modified optimized median of 3 quicksort, with network sorting for lists of size up to 16 and for finding the median. I have tried using the O(N) approach to finding the median, but sorting normally was faster.
Can I get some advice on how to make this faster?
Also, can anyone link fast sorting algorithms? I want to compare them to mine and see if there are faster, and if they are, how I can improve mine. The first like 1000 lines is the network sorting (I made a program to automatically generate code for the network sorting, I am not a madman), and the final 20ish is testing how fast it is. On my laptop, it sorts 100,000 random numbers in about 0.192 seconds and 1,000,000 random numbers in about 2.754 seconds. (Note that python's time is not 100% accurate. I used multiple tests and found the average.)

I have compared my code to mergesort, heapsort, other quicksorts, timsort, and radix sort, but none of them seem to be close to beating my code. However, that is likely because they were from how-to sites, and were not optimized. Sadly, most people who care about having a quick sorting algorithm seem to write it in Java, C or C++ which I can't really compare. So, I would appreciate any other optimized sorting algorithms, or even suggestions to my original code.

#importing

import math
import random
import time

#this is the sorting network (scroll a bunch, this is like 1000 lines)

def sorting_network(lst):
    l = len(lst)

    if l < 9:
        if l < 5:
            if l < 3:
                if not l or l == 1:
                    return lst
                else:
                    a = lst[0]
                    b = lst[1]
                    
                    if a > b:
                        a, b = b, a
                    
                    return [a, b]
            else:
                if l == 3:
                    a = lst[0]
                    b = lst[1]
                    c = lst[2]
                    
                    if a > b:
                        a, b = b, a
                    if b > c:
                        b, c = c, b
                    if a > b:
                        a, b = b, a

                    return [a, b, c]

                else:
                    a = lst[0]
                    b = lst[1]
                    c = lst[2]
                    d = lst[3]
                    
                    if a > b:
                        a, b = b, a
                    if c > d:
                        c, d = d, c
                    if a > c:
                        a, c = c, a
                    if b > d:
                        b, d = d, b
                    if b > c:
                        b, c = c, b

                    return [a, b, c, d]

        else:
            if l < 7:
                if l == 5:
                    a = lst[0]
                    b = lst[1]
                    c = lst[2]
                    d = lst[3]
                    e = lst[4]
                    
                    if a > d:
                        a, d = d, a
                    if b > e:
                        b, e = e, b
                    if a > b:
                        a, b = b, a
                    if c > e:
                        c, e = e, c
                    if b > c:
                        b, c = c, b
                    if d > e:
                        d, e = e, d
                    if c > d:
                        c, d = d, c

                    return [a, b, c, d, e]
                else:
                    a = lst[0]
                    b = lst[1]
                    c = lst[2]
                    d = lst[3]
                    e = lst[4]
                    f = lst[5]
                    
                    if a > f:
                        a, f = f, a
                    if b > d:
                        b, d = d, b
                    if c > e:
                        c, e = e, c
                    if b > c:
                        b, c = c, b
                    if d > e:
                        d, e = e, d
                    if a > d:
                        a, d = d, a
                    if c > f:
                        c, f = f, c
                    if a > b:
                        a, b = b, a
                    if c > d:
                        c, d = d, c
                    if e > f:
                        e, f = f, e
                    if b > c:
                        b, c = c, b
                    if d > e:
                        d, e = e, d

                    return [a, b, c, d, e, f]
            else:
                if l == 7:
                    a = lst[0]
                    b = lst[1]
                    c = lst[2]
                    d = lst[3]
                    e = lst[4]
                    f = lst[5]
                    g = lst[6]
                    
                    if a > b:
                        a, b = a, b
                    if c > d:
                        c, d = d, c
                    if e > f:
                        e, f = f, e
                    if a > c:
                        a, c = c, a
                    if b > e:
                        b, e = e, b
                    if d > g:
                        d, g = g, d
                    if a > b:
                        a, b = b, a
                    if c > f:
                        c, f = f, c
                    if d > e:
                        d, e = e, d
                    if b > c:
                        b, c = c, b
                    if e > g:
                        e, g = g, e
                    if c > d:
                        c, d = d, c
                    if e > f:
                        e, f = f, e
                    if b > c:
                        b, c = c, b
                    if d > e:
                        d, e = e, d
                    if f > g:
                        f, g = g, f
                    
                    return [a, b, c, d, e, f, g]
                else:
                    a = lst[0]
                    b = lst[1]
                    c = lst[2]
                    d = lst[3]
                    e = lst[4]
                    f = lst[5]
                    g = lst[6]
                    h = lst[7]
                    
                    if a > c:
                        a, c = c, a
                    if b > d:
                        b, d = d, b
                    if e > g:
                        e, g = g, e
                    if f > h:
                        f, h = h, f
                    if a > e:
                        a, e = e, a
                    if b > f:
                        b, f = f, b
                    if c > g:
                        c, g = g, c
                    if d > h:
                        d, h = h, d
                    if a > b:
                        a, b = b, a
                    if c > d:
                        c, d = d, c
                    if e > f:
                        e, f = f, e
                    if g > h:
                        g, h = h, g
                    if c > e:
                        c, e = e, c
                    if d > f:
                        d, f = f, d
                    if b > e:
                        b, e = e, b
                    if d > g:
                        d, g = g, d
                    if b > c:
                        b, c = c, b
                    if d > e:
                        d, e = e, d
                    if f > g:
                        f, g = g, f

                    return [a, b, c, d, e, f, g, h]

    else:
        if l < 13:
            if l < 11:
                if l == 9:
                    a = lst[0]
                    b = lst[1]
                    c = lst[2]
                    d = lst[3]
                    e = lst[4]
                    f = lst[5]
                    g = lst[6]
                    h = lst[7]
                    i = lst[8]
                    
                    if a > d:
                        a, d = d, a
                    if b > h:
                        b, h = h, b
                    if c > f:
                        c, f = f, c
                    if e > i:
                        e, i = i, e
                    if a > h:
                        a, h = h, a
                    if c > e:
                        c, e = e, c
                    if d > i:
                        d, i = i, d
                    if f > g:
                        f, g = g, f
                    if a > c:
                        a, c = c, a
                    if b > d:
                        b, d = d, b
                    if e > f:
                        e, f = f, e
                    if h > i:
                        h, i = i, h
                    if b > e:
                        b, e = e, b
                    if d > g:
                        d, g = g, d
                    if f > h:
                        f, h = h, f
                    if a > b:
                        a, b = b, a
                    if c > e:
                        c, e = e, c
                    if d > f:
                        d, f = f, d
                    if g > i:
                        g, i = i, g
                    if c > d:
                        c, d = d, c
                    if e > f:
                        e, f = f, e
                    if g > h:
                        g, h = h, g
                    if b > c:
                        b, c = c, b
                    if d > e:
                        d, e = e, d
                    if f > g:
                        f, g = g, f

                    return [a, b, c, d, e, f, g, h, i]

                else:
                    a = lst[0]
                    b = lst[1]
                    c = lst[2]
                    d = lst[3]
                    e = lst[4]
                    f = lst[5]
                    g = lst[6]
                    h = lst[7]
                    i = lst[8]
                    j = lst[9]
                    
                    if a > i:
                        a, i = i, a
                    if b > j:
                        b, j = j, b
                    if c > h:
                        c, h = h, c
                    if d > f:
                        d, f = f, d
                    if e > g:
                        e, g = g, e
                    if a > c:
                        a, c = c, a
                    if b > e:
                        b, e = e, b
                    if f > i:
                        f, i = i, f
                    if h > j:
                        h, j = j, h
                    if a > d:
                        a, d = d, a
                    if c > e:
                        c, e = e, c
                    if f > h:
                        f, h = h, f
                    if g > j:
                        g, j = j, g
                    if a > b:
                        a, b = b, a
                    if d > g:
                        d, g = g, d
                    if i > j:
                        i, j = j, i
                    if b > f:
                        b, f = f, b
                    if c > d:
                        c, d = d, c
                    if e > i:
                        e, i = i, e
                    if g > h:
                        g, h = h, g
                    if b > c:
                        b, c = c, b
                    if d > f:
                        d, f = f, d
                    if e > g:
                        e, g = g, e
                    if h > i:
                        h, i = i, h
                    if c > d:
                        c, d = d, c
                    if e > f:
                        e, f = f, e
                    if g > h:
                        g, h = h, g
                    if d > e:
                        d, e = e, d
                    if f > g:
                        f, g = g, f

                    return [a, b, c, d, e, f, g, h, i, j]

            else:
                if l == 11:
                    a = lst[0]
                    b = lst[1]
                    c = lst[2]
                    d = lst[3]
                    e = lst[4]
                    f = lst[5]
                    g = lst[6]
                    h = lst[7]
                    i = lst[8]
                    j = lst[9]
                    k = lst[10]

                    if b > g:
                        b, g = g, b
                    if c > e:
                        c, e = e, c
                    if d > h:
                        d, h = h, d
                    if f > i:
                        f, i = i, f
                    if a > b:
                        a, b = b, a
                    if d > f:
                        d, f = f, d
                    if e > k:
                        e, k = k, e
                    if g > j:
                        g, j = j, g
                    if h > i:
                        h, i = i, h
                    if b > d:
                        b, d = d, b
                    if c > f:
                        c, f = f, c
                    if e > h:
                        e, h = h, e
                    if i > k:
                        i, k = k, i
                    if a > e:
                        a, e = e, a
                    if b > c:
                        b, c = c, b
                    if d > h:
                        d, h = h, d
                    if f > j:
                        f, j = j, f
                    if g > i:
                        g, i = i, g
                    if a > b:
                        a, b = b, a
                    if c > g:
                        c, g = g, c
                    if e > f:
                        e, f = f, e
                    if h > i:
                        h, i = i, h
                    if j > k:
                        j, k = k, j
                    if c > e:
                        c, e = e, c
                    if d > g:
                        d, g = g, d
                    if f > h:
                        f, h = h, f
                    if i > j:
                        i, j = j, i
                    if b > c:
                        b, c = c, b
                    if d > e:
                        d, e = e, d
                    if f > g:
                        f, g = g, f
                    if h > i:
                        h, i = i, h
                    if c > d:
                        c, d = d, c
                    if e > f:
                        e, f = f, e
                    if g > h:
                        g, h = h, g

                    return [a, b, c, d, e, f, g, h, i, j, k]

                else:
                    a = lst[0]
                    b = lst[1]
                    c = lst[2]
                    d = lst[3]
                    e = lst[4]
                    f = lst[5]
                    g = lst[6]
                    h = lst[7]
                    i = lst[8]
                    j = lst[9]
                    k = lst[10]
                    l = lst[11]
                    
                    if b > h:
                        b, h = h, b
                    if c > g:
                        c, g = g, c
                    if d > l:
                        d, l = l, d
                    if e > k:
                        e, k = k, e
                    if f > j:
                        f, j = j, f
                    if a > b:
                        a, b = b, a
                    if c > f:
                        c, f = f, c
                    if d > e:
                        d, e = e, d
                    if g > j:
                        g, j = j, g
                    if h > i:
                        h, i = i, h
                    if k > l:
                        k, l = l, k
                    if a > c:
                        a, c = c, a
                    if b > g:
                        b, g = g, b
                    if f > k:
                        f, k = k, f
                    if j > l:
                        j, l = l, j
                    if a > d:
                        a, d = d, a
                    if b > c:
                        b, c = c, b
                    if e > g:
                        e, g = g, e
                    if f > h:
                        f, h = h, f
                    if i > l:
                        i, l = l, i
                    if j > k:
                        j, k = k, j
                    if b > e:
                        b, e = e, b
                    if d > f:
                        d, f = f, d
                    if g > i:
                        g, i = i, g
                    if h > k:
                        h, k = k, h
                    if b > d:
                        b, d = d, b
                    if c > f:
                        c, f = f, c
                    if g > j:
                        g, j = j, g
                    if i > k:
                        i, k = k, i
                    if c > d:
                        c, d = d, c
                    if e > f:
                        e, f = f, e
                    if g > h:
                        g, h = h, g
                    if i > j:
                        i, j = j, i
                    if e > g:
                        e, g = g, e
                    if f > h:
                        f, h = h, f
                    if d > e:
                        d, e = e, d
                    if f > g:
                        f, g = g, f
                    if h > i:
                        h, i = i, h

                    return [a, b, c, d, e, f, g, h, i, k, l]
        else:
            if l < 15:
                if l == 13:
                    a = lst[0]
                    b = lst[1]
                    c = lst[2]
                    d = lst[3]
                    e = lst[4]
                    f = lst[5]
                    g = lst[6]
                    h = lst[7]
                    i = lst[8]
                    j = lst[9]
                    k = lst[10]
                    l = lst[11]
                    m = lst[12]
                    
                    if a > m:
                        a, m = m, a
                    if b > k:
                        b, k = k, b
                    if c > j:
                        c, j = j, c
                    if d > h:
                        d, h = h, d
                    if f > l:
                        f, l = l, f
                    if g > i:
                        g, i = i, g
                    if b > g:
                        b, g = g, b
                    if c > d:
                        c, d = d, c
                    if e > l:
                        e, l = l, e
                    if h > j:
                        h, j = j, h
                    if i > k:
                        i, k = k, i
                    if a > e:
                        a, e = e, a
                    if b > c:
                        b, c = c, b
                    if d > g:
                        d, g = g, d
                    if h > i:
                        h, i = i, h
                    if j > k:
                        j, k = k, j
                    if l > m:
                        l, m = m, l
                    if e > g:
                        e, g = g, e
                    if f > j:
                        f, j = j, f
                    if i > l:
                        i, l = l, i
                    if k > m:
                        k, m = m, k
                    if a > f:
                        a, f = f, a
                    if d > i:
                        d, i = i, d
                    if e > h:
                        e, h = h, e
                    if g > l:
                        g, l = l, g
                    if j > k:
                        j, k = k, j
                    if a > b:
                        a, b = b, a
                    if c > f:
                        c, f = f, c
                    if g > j:
                        g, j = j, g
                    if h > i:
                        h, i = i, h
                    if k > l:
                        k, l = l, k
                    if b > d:
                        b, d = d, b
                    if c > e:
                        c, e = e, c
                    if f > g:
                        f, g = g, f
                    if j > k:
                        j, k = k, j
                    if b > c:
                        b, c = c, b
                    if d > e:
                        d, e = e, d
                    if f > h:
                        f, h = h, f
                    if g > i:
                        g, i = i, g
                    if c > d:
                        c, d = d, c
                    if e > f:
                        e, f = f, e
                    if g > h:
                        g, h = h, g
                    if i > j:
                        i, j = j, i
                    if d > e:
                        d, e = e, d
                    if f > g:
                        f, g = g, f

                    return [a, b, c, d, e, f, g, h, i, j, k, l, m]

                else:
                    a = lst[0]
                    b = lst[1]
                    c = lst[2]
                    d = lst[3]
                    e = lst[4]
                    f = lst[5]
                    g = lst[6]
                    h = lst[7]
                    i = lst[8]
                    j = lst[9]
                    k = lst[10]
                    l = lst[11]
                    m = lst[12]
                    n = lst[13]
                    
                    if a > g:
                        a, g = g, a
                    if b > l:
                        b, l = l, b
                    if c > m:
                        c, m = m, c
                    if d > k:
                        d, k = k, d
                    if e > f:
                        e, f = f, e
                    if h > n:
                        h, n = n, h
                    if i > j:
                        i, j = j, i
                    if b > c:
                        b, c = c, b
                    if d > h:
                        d, h = h, d
                    if e > i:
                        e, i = i, e
                    if f > j:
                        f, j = j, f
                    if g > k:
                        g, k = k, g
                    if l > m:
                        l, m = m, l
                    if a > e:
                        a, e = e, a
                    if b > d:
                        b, d = d, b
                    if f > g:
                        f, g = g, f
                    if h > i:
                        h, i = i, h
                    if j > n:
                        j, n = n, j
                    if k > m:
                        k, m = m, k
                    if a > b:
                        a, b = b, a
                    if c > j:
                        c, j = j, c
                    if d > h:
                        d, h = h, d
                    if e > l:
                        e, l = l, e
                    if g > k:
                        g, k = k, g
                    if m > n:
                        m, n = n, m
                    if c > f:
                        c, f = f, c
                    if e > h:
                        e, h = h, e
                    if g > j:
                        g, j = j, g
                    if i > l:
                        i, l = l, i
                    if b > c:
                        b, c = c, b
                    if d > e:
                        d, e = e, d
                    if g > h:
                        g, h = h, g
                    if j > k:
                        j, k = k, j
                    if l > m:
                        l, m = m, l
                    if b > d:
                        b, d = d, b
                    if c > e:
                        c, e = e, c
                    if f > g:
                        f, g = g, f
                    if h > i:
                        h, i = i, h
                    if j > l:
                        j, l = l, j
                    if k > m:
                        k, m = m, k
                    if c > d:
                        c, d = d, c
                    if e > h:
                        e, h = h, e
                    if g > j:
                        g, j = j, g
                    if k > l:
                        k, l = l, k
                    if e > f:
                        e, f = f, e
                    if g > h:
                        g, h = h, g
                    if i > j:
                        i, j = j, i
                    if d > e:
                        d, e = e, d
                    if f > g:
                        f, g = g, f
                    if h > i:
                        h, i = i, h
                    if j > k:
                        j, k = k, j

                    return [a, b, c, d, e, f, g, h, i, j, k, l, m, n]

            else:
                if l == 15:
                    a = lst[0]
                    b = lst[1]
                    c = lst[2]
                    d = lst[3]
                    e = lst[4]
                    f = lst[5]
                    g = lst[6]
                    h = lst[7]
                    i = lst[8]
                    j = lst[9]
                    k = lst[10]
                    l = lst[11]
                    m = lst[12]
                    n = lst[13]
                    o = lst[14]
                    
                    if b > c:
                        b, c = c, b
                    if d > k:
                        d, k = k, d
                    if e > o:
                        e, o = o, e
                    if f > i:
                        f, i = i, f
                    if g > n:
                        g, n = n, g
                    if h > m:
                        h, m = m, h
                    if j > l:
                        j, l = l, j
                    if a > o:
                        a, o = o, a
                    if b > f:
                        b, f = f, b
                    if c > i:
                        c, i = i, c
                    if d > h:
                        d, h = h, d
                    if g > j:
                        g, j = j, g
                    if k > m:
                        k, m = m, k
                    if l > n:
                        l, n = n, l
                    if a > h:
                        a, h = h, a
                    if b > g:
                        b, g = g, b
                    if c > j:
                        c, j = j, c
                    if e > k:
                        e, k = k, e
                    if f > l:
                        f, l = l, f
                    if i > n:
                        i, n = n, i
                    if m > o:
                        m, o = o, m
                    if a > g:
                        a, g = g, a
                    if c > e:
                        c, e = e, c
                    if d > f:
                        d, f = f, d
                    if h > l:
                        h, l = l, h
                    if i > k:
                        i, k = k, i
                    if j > m:
                        j, m = m, j
                    if n > o:
                        n, o = o, n
                    if a > d:
                        a, d = d, a
                    if b > c:
                        b, c = c, b
                    if e > h:
                        e, h = h, e
                    if f > j:
                        f, j = j, f
                    if g > i:
                        g, i = i, g
                    if k > l:
                        k, l = l, k
                    if m > n:
                        m, n = n, m
                    if a > b:
                        a, b = b, a
                    if c > d:
                        c, d = d, c
                    if e > g:
                        e, g = g, e
                    if h > j:
                        h, j = j, h
                    if k > m:
                        k, m = m, k
                    if l > n:
                        l, n = n, l
                    if b > c:
                        b, c = c, b
                    if d > f:
                        d, f = f, d
                    if i > k:
                        i, k = k, i
                    if l > m:
                        l, m = m, l
                    if d > e:
                        d, e = e, d
                    if f > g:
                        f, g = g, f
                    if h > i:
                        h, i = i, h
                    if j > k:
                        j, k = k, j
                    if c > d:
                        c, d = d, c
                    if e > f:
                        e, f = f, e
                    if g > h:
                        g, h = h, g
                    if i > j:
                        i, j = j, i
                    if k > l:
                        k, l = l, k
                    if f > g:
                        f, g = g, f
                    if h > i:
                        h, i = i, h

                    return [a, b, c, d, e, f, g, h, i, j, k, l, m, n, o]

                else:
                    a = lst[0]
                    b = lst[1]
                    c = lst[2]
                    d = lst[3]
                    e = lst[4]
                    f = lst[5]
                    g = lst[6]
                    h = lst[7]
                    i = lst[8]
                    j = lst[9]
                    k = lst[10]
                    l = lst[11]
                    m = lst[12]
                    n = lst[13]
                    o = lst[14]
                    p = lst[15]
                    
                    if a > n:
                        a, n = n, a
                    if b > m:
                        b, m = m, b
                    if c > p:
                        c, p = p, c
                    if d > o:
                        d, o = o, d
                    if e > i:
                        e, i = i, e
                    if f > g:
                        f, g = g, f
                    if h > l:
                        h, l = l, h
                    if j > k:
                        j, k = k, j
                    if a > f:
                        a, f = f, a
                    if b > h:
                        b, h = h, b
                    if c > j:
                        c, j = j, c
                    if d > e:
                        d, e = e, d
                    if g > n:
                        g, n = n, g
                    if i > o:
                        i, o = o, i
                    if k > p:
                        k, p = p, k
                    if l > m:
                        l, m = m, l
                    if a > b:
                        a, b = b, a
                    if c > d:
                        c, d = d, c
                    if e > f:
                        e, f = f, e
                    if g > i:
                        g, i = i, g
                    if h > j:
                        h, j = j, h
                    if k > l:
                        k, l = l, k
                    if m > n:
                        m, n = n, m
                    if o > p:
                        o, p = p, o
                    if a > c:
                        a, c = c, a
                    if b > d:
                        b, d = d, b
                    if e > k:
                        e, k = k, e
                    if f > l:
                        f, l = l, f
                    if g > h:
                        g, h = h, g
                    if i > j:
                        i, j = j, i
                    if m > o:
                        m, o = o, m
                    if n > p:
                        n, p = p, n
                    if b > c:
                        b, c = c, b
                    if d > m:
                        d, m = m, d
                    if e > g:
                        e, g = g, e
                    if f > h:
                        f, h = h, f
                    if i > k:
                        i, k = k, i
                    if j > l:
                        j, l = l, j
                    if n > o:
                        n, o = o, n
                    if b > e:
                        b, e = e, b
                    if c > g:
                        c, g = g, c
                    if f > i:
                        f, i = i, f
                    if h > k:
                        h, k = k, h
                    if j > n:
                        j, n = n, j
                    if l > o:
                        l, o = o, l
                    if c > e:
                        c, e = e, c
                    if d > g:
                        d, g = g, d
                    if j > m:
                        j, m = m, j
                    if l > n:
                        l, n = n, l
                    if d > f:
                        d, f = f, d
                    if g > i:
                        g, i = i, g
                    if h > j:
                        h, j = j, h
                    if k > m:
                        k, m = m, k
                    if d > e:
                        d, e = e, d
                    if f > g:
                        f, g = g, f
                    if h > i:
                        h, i = i, h
                    if j > k:
                        j, k = k, j
                    if l > m:
                        l, m = m, l
                    if g > h:
                        g, h = h, g
                    if i > j:
                        i, j = j, i

                    return [a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p]

#and this is the quicksort algorithm!

def swiftsort(lst):
    l = len(lst)
    
    if l < 17:
        return sorting_network(lst)
    elif l < 128:
        a = lst[0]
        b = lst[l // 2]
        c = lst[-1]
        if a <= b <= c or c <= b <= a:
            split = b
        elif b <= c <= a or a <= c <= b:
            split = c
        else:
            split = a
    elif l < 8192:
        a = [lst[0], lst[l // 8], lst[2 * l // 8], lst[3 * l // 8], lst[4 * l // 8], lst[5 * l // 8], lst[6 * l // 8], lst[7 * l // 8], lst[-1]]
        split = sorting_network(lst)[4]
    else:
        a = [lst[0]]
        
        for x in range(1, 32):
            a.append(lst[x * l // 32])

        a.append(lst[-1])
        split = swiftsort(a)[16]


    lst1 = []
    lst2 = []
    mid = []

    for x in lst:
        if x < split:
            lst1.append(x)
        elif x == split:
            mid.append(x)
        else:
            lst2.append(x)

    return swiftsort(lst1) + mid + swiftsort(lst2)

#This is for testing the time of my algorithm.
length = 100000
runs = 60
test_list = [random.randint(1, length) for _ in range(length)]
t = 0

for _ in range(runs):
    start = time.time()
    sort = swiftsort(test_list)
    end = time.time()
    t += end - start

print(t / runs)
\$\endgroup\$
12
  • \$\begingroup\$ Python is not a good choice for benchmarking algorithms, since it is an interpretive language and slow. I would recommend C or C++ compiled with an optimizing compiler. \$\endgroup\$ – rcgldr Mar 21 at 22:21
  • \$\begingroup\$ Welcome to Code Review@SE. I have made a sorting algorithm… I don't think so - you tried to implement quicksort, but left out base cases, for starters. Try print(swiftsort(list('abramccarthybra'))). (…made a sorting algorithm in python conventional wordings include coded, implemented, crafted an implementation.) \$\endgroup\$ – greybeard Mar 21 at 22:41
  • \$\begingroup\$ Ok, I have edited my title (is it better now?). Also, I have removed the insertion sort part because I wasn't using it anymore, and added the network sorting from 13-16. It should work now! I'll also try to add comments to the code. EDIT: I've added a few comments to seperate my code out. \$\endgroup\$ – Sola Sky Mar 21 at 23:10
  • \$\begingroup\$ I do find the title much improved. Remaining issue with it: There's little need to repeat tags. I have removed the insertion sort part funny - I thought the "almost median of 32" uses it. \$\endgroup\$ – greybeard Mar 21 at 23:38
  • \$\begingroup\$ I've changed the insertion sort part to my quicksort algorithm itself because it was faster. Also, I've edited my post. \$\endgroup\$ – Sola Sky Mar 21 at 23:45
1
\$\begingroup\$

(This begins with opinions about the way the partition&network sort presented by Sola Sky is coded.
I intend to get to comments on resource requirements - don't hold your breath.)

In your question, you provide context: the what & why.
Do so in the code! Python has got it right providing docstrings, a documentation mechanism succeeding in making it unlikely for code to be separated from its documentation. (It even is available for introspection.) You may find yourself wanting to rename sorting_network() after writing its docstring.
Docstrings feature in the Style Guide for Python Code, which you seem aware of.
It contains good advice such as comments are unnecessary and in fact distracting if they state the obvious -
#importing is a non-comment.
math currently is not used.
(random and time are "just" used in the benchmark - more on this later.)

sorting_network(lst):
I notice you do not use Type Hints.
In the "decision tree", there is no need for an else following a return. One advantage of doing without is less code indentation.
I'd have liked to read, in the code, about the type of comparison network your generator constructs - I didn't try to figure it out, no comment on using networks of optimal depth or comparators(/comparisons?) here. My IDE "counts" 60 for len 16 - best known I find.

(and this is the quicksort algorithm! To split a hair, I expect quicksort to sort in-place (and, hopefully, with additional space dominated by the size of input). I'd use partition sort.)
swiftsort(lst):
return-else, again
"Habitually", quicksort is coded with pivot selection and partition factored out.
The "between-comparisons" are very readable -
split = b if a <= b == b <= c else c if b <= c == c <= a else a repeats one comparison instead of potentially four.
Prefer a for in comprehensions over enumerating the elements or appending them in a loop:
[lst[l_ * i // 8] for i in range(9) for l_ in (l - 1,)]
(The second for just introduces l_ (=l-1) "in-line")
"The 8192-limit" looks somewhat arbitrary - how about using one item less than the number of bits in ls representation?

    samples = (int.bit_length(l) // 2) * 2 - 1
    samples = [lst[(l - 1) * i // (samples - 1)] for i in range(samples)]
    pivot = sorted(samples)[len(samples)//2]

(I could write (int.bit_length(l)&~1) - can I read it? You? The maintenance programmer?) (For no more than 16 items, swiftsort()/sorting_network() look advantageous. Not so sure immediately above.)
(Oh, look, you could do away with "the 128 comparison", too.)

While lst is a so-so name to begin with, lst1/lst2 just don't do: I'd prefer before&after over preceding&following for brevity, and over smaller/bigger for not interpreting the order (which you may want redefinable via mechanisms like an optional comparator or a reverse flag like sorted()).
In languages providing a shorter syntax for this, I might prefer the equivalent of
(before if x < split else mid if x == split else after).append(x) to stress the difference is in picking the sequence, not in the operation on it or the parameter.
In a "production strength sort", I'd try to avoid worst case resource consumption: recurse on the shorter of before&after, iterate on the other. Doesn't look any simpler with three-way partition.

With Python code in files, there are named modules: the module name is the file name "without the trailing .py". The module a python interpreter is started to execute has the name "__main__" during execution. This allows keeping short tests or benchmarks in code intended to be used library style:

# This is for testing the time of my algorithm.
if __name__== '__main__':
    import random  # place "non-library imports" here
    # some test code

Assessing resource usage to expect in general and timing, micro-benchmarking in particular are interesting cans of worms.
Let me just mention timeit and Cython.
And that the bigger of the problem sizes you chose fits into (L3) cache of contemporary general purpose processors.

\$\endgroup\$
3
  • \$\begingroup\$ The more I think about it, the less I like swiftsort() to use additional lists instead of sorting in-place. \$\endgroup\$ – greybeard Mar 22 at 20:56
  • \$\begingroup\$ Ok, thanks! The reason I didn't do in place was because it was harder to code the partitions, and it was almost 2x slower. However, that might be because I'm a beginner coder. If you could help me write quicksort inplace without affecting the speed heavily, I would appreciate it a lot. Also, I'd definitely change the partitions to the bit_length suggestion you made. I'd try to make better variable names, type hints and more. Thanks a lot! \$\endgroup\$ – Sola Sky Mar 22 at 21:22
  • \$\begingroup\$ The main pretext I have for not doing so is that when you are doing three-way partition anyway, you may as well go dual pivot. (Not true by a mile ordering unique values, but then you'd know len(mid) at the outset of partition.) I'd be tempted even more if I could adapt the ordering network code generator too: that would need to generate code ordering in-place, too. Note that posting on SE puts contents under Creative Commons. \$\endgroup\$ – greybeard Mar 23 at 6:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.