QuickSort is one of the mostly used sort algorithm in CS. It has the best average performance.

The algorithm is very simple and elegant , its a recursive algorithm, at each recursive, one pivot is selected and divide the array into two sub arrays, one less than the pivot and another one bigger than it.

When there is no division can happen, the list is sorted.

 
import unittest
 
def qsort(start, end , list):
    if start >= end:
        return
    pivot = partition(start, end, list)
 
    qsort(start, pivot - 1, list)
    qsort(pivot + 1 , end, list)
    return list
 
def partition(start, end, list):
    #print "partition from " , start, "to " , end
    last = list[end]
 
    i = start
    for j in range(start,end):
        if list[j] < last:        
            #swap i j
            list[i],list[j] = list[j],list[i]
 
            i = i + 1
 
    #swap last and i
    list[i],list[end] = list[end],list[i]
    #print "sorted:", last
    return i
 
 
def qsort2(L):  
    if L == []: return []  
    return     qsort2([x for x in L[1:] if x< L[0]]) + L[0:1] + qsort2([x for x in L[1:] if x>=L[0]])  
 
 
class TestSort(unittest.TestCase):
    def setUp(self):
        self.list = [23,1,3,3,5,456,34,35,4654,7354,242,321]        
 
    def tearDown(self):
        del self.list
 
    def test_sort1(self):
 
        qsort(0, len(self.list) - 1 , self.list)
 
        for i, element in enumerate(self.list):
            if i < len(self.list) - 1:
                self.assertTrue(element <= self.list[i + 1])
 
    def test_sort2(self):
        self.list = qsort2(self.list)
 
        for i, element in enumerate(self.list):
            if i < len(self.list) - 1:
                self.assertTrue(element <= self.list[i + 1])
 
if __name__ == '__main__':
    unittest.main()
 
 
 
 

The first one is the classic way , contains low level operations. The second one is more expressive and clear. This is the express power of Python.

We use the "list filter expression" that Python provided for convenience. It select items from the list that less than the pivot and select the elements bigger than pivot , then concatenate them together.