Fastest way to sort in Python

Question

What is the fastest way to sort an array of whole integers bigger than 0 and less than 100000 in Python? But not using the built in functions like sort.

Im looking at the possibility to combine 2 sport functions depending on input size.

Answer 1

Since you know the range of numbers, you can use Counting Sort which will be linear in time.

Answer 2

The built in functions are best, but since you can't use them have a look at this:

http://en.wikipedia.org/wiki/Quicksort

Answer 3

If you are interested in asymptotic time, then counting sort or radix sort provide good performance.

However, if you are interested in wall clock time you will need to compare performance between different algorithms using your particular data sets, as different algorithms perform differently with different datasets. In that case, its always worth trying quicksort:

def qsort(inlist):
    if inlist == []: 
        return []
    else:
        pivot = inlist[0]
        lesser = qsort([x for x in inlist[1:] if x < pivot])
        greater = qsort([x for x in inlist[1:] if x >= pivot])
        return lesser + [pivot] + greater

Answer 4

Early versions of Python used a hybrid of samplesort (a variant of quicksort with large sample size) and binary insertion sort as the built-in sorting algorithm. This proved to be somewhat unstable. S0, from python 2.3 onward uses adaptive mergesort algorithm.

Order of mergesort (average) = O(nlogn). Order of mergesort (worst) = O(nlogn). But Order of quick sort (worst) = n*2

if you uses list=[ .............. ]

list.sort() uses mergesort algorithm.

For comparison between sorting algorithm you can read wiki

For detail comparison comp

Answer 5

We can use count sort using a dictionary to minimize the additional space usage, and keep the running time low as well. The count sort is much slower for small sizes of the input array because of the python vs C implementation overhead. The count sort starts to overtake the regular sort when the size of the array (COUNT) is about 1 million.

If you really want huge speedups for smaller size inputs, implement the count sort in C and call it from Python.

(Fixed a bug which Aaron (+1) helped catch ...) The python only implementation below compares the 2 approaches...

import random
import time

COUNT = 3000000

array = [random.randint(1,100000) for i in range(COUNT)]
random.shuffle(array)

array1 = array[:]

start = time.time()
array1.sort()
end = time.time()
time1 = (end-start)
print 'Time to sort = ', time1*1000, 'ms'

array2 = array[:]

start = time.time()
ardict = {}
for a in array2:
    try:
        ardict[a] += 1
    except:
        ardict[a] = 1

indx = 0
for a in sorted(ardict.keys()):
    b = ardict[a]
    array2[indx:indx+b] = [a for i in xrange(b)]
    indx += b

end = time.time()
time2 = (end-start)
print 'Time to count sort = ', time2*1000, 'ms'

print 'Ratio =', time2/time1

Answer 6

Radix sort theoretically runs in linear time (sort time grows roughly in direct proportion to array size ), but in practice Quicksort is probably more suited, unless you're sorting absolutely massive arrays.

If you want to make quicksort a bit faster, you can use insertion sort] when the array size becomes small.

It would probably be helpful to understand the concepts of algorithmic complexity and Big-O notation too.