have I invented a new sorting algorithm? or is this the same as quicksort

Question

I made an algorithm for sorting but I then I thought perhaps I had just reinvented quicksort.

However I heard quicksort is O(N^2) worst case; I think my algorithm should be only O(NLogN) worst case.

Is this the same as quicksort?

The algorithm works by swapping values so that all values smaller than the median are moved to the left of the array. It then works recursively on each side.

The algorithm starts with i=0, j = n-1

i and j move towards each other with list[i] and list[j] being swapped if necessary.

Here is some code for the first iteration before the recursion:

_list = [1,-4,2,-5,3,-6]

def in_place(_list,i,j,median):
    while i<j:
        a,b = _list[i],_list[j]
        if (a<median and b>=median):
            i+=1
            j-=1
        elif (a>=median and b<median):
            _list[i],_list[j]=b,a
            i+=1
            j-=1
        elif a<median:
            i+=1
        else:
            j-=1
    print "changed to ", _list



def get_median(_list):
    #approximate median in O(N) with O(1) space
    return -4

median = get_median(_list)
in_place(_list,0,len(_list)-1,median)

"""
changed1 to  [-6, -5, 2, -4, 3, 1]
"""

Answer 1

http://en.wikipedia.org/wiki/Quicksort#Selection-based_pivoting

Conversely, once we know a worst-case O(n) selection algorithm is available, we can use it to find the ideal pivot (the median) at every step of quicksort, producing a variant with worst-case O(n log n) running time. In practical implementations, however, this variant is considerably slower on average.

Another variant is to choose the Median of Medians as the pivot element instead of the median itself for partitioning the elements. While maintaining the asymptotically optimal run time complexity of O(n log n) (by preventing worst case partitions), it is also considerably faster than the variant that chooses the median as pivot.

Answer 2

For starters, I assume there is other code not shown, as I'm pretty sure that the code you've shown on its own would not work.

I'm sorry to steal your fire, but I'm afraid what code you do show seems to be Quicksort, and not only that, but the code seems to possibly suffer from some bugs.

Consider the case of sorting a list of identical elements. Your _in_place method, which seems to be what is traditionally called partition in Quicksort, would not move any elements correctly, but at the end the j and i seem to reflect the list having only one partition containing the whole list, in which case you would recurse again on the whole list forever. My guess is, as as mentioned, you don't return anything from it, or seem to actually fully sort anywhere, so I am left guessing how this would be used.

I'm afraid using the real median for Quicksort is not only a possibly fairly slow strategy in the average case, it also doesn't avoid the O(n^2) worst case, again a list of identical elements would provide such a worst case. However, I think a three way partition Quicksort with such a median selection algorithm would guarantee O(n*log n) time. Nonetheless, this is a known option for pivot choice and not a new algorithm.

In short, this appears to be an incomplete and possibly buggy Quicksort, and without three way partitioning, using the median would not guarantee you O(n*log n). However, I do feel that it is a good thing and worth congratulations that you did think of the idea of using the median yourself - even if it has been thought of by others before.