Sorting Algorithms

Module containing the most common sorting algorithms
  • bubble sort
  • selection sort
  • insertion sort
  • shell sort
  • quicksort
  • merge sort
  • heapsort

For the record, Python built-in sorted uses by default timsort which is a hybrid stable sorting algorithm, running in O(n) for best case (list already sorted) to O(n log n). It does so by taking advantage of the fact that real-life lists often have some partial ordering.


In this algo, the i-th pass starts at the first element and compare sequencially each element to the next, swapping them if necessary, up to n-i. The biggest element ‘bubbles up’ to the n-i position. This runs in O(n^2): n-1 passes of O(n) comparisons.

Note the use of the pythonic swap operation “a, b = b, a”, not requiring the use of a temporary storage variable.


The insertion sort uses another strategy: at the i-th pass, the i first terms are sorted and it inserts the i + 1 term where it belongs by shifting right all elements greater one notch right to create a gap to insert it. It also runs in O(n^2)

src.classic_algo.sort.merge(a, b)[source]

helper function used by merge_sort combines two sorted lists into one sorted list


Based on the divide and conquer approach, this algorithm runs in O(n log n). The array is split by the middle and each half is recursively sorted using merge_sort. The two sorted halves are then efficiently merged using the helper function above.

src.classic_algo.sort.partition_helper(a, first, last)[source]

A left_mark index are initiated at the leftmost index available (ie not the pivot) and a right_mark at the rightmost. The left_mark is shifted right as long as a[left_mark] < pivot and the right_mark left as long as a[right_mark] > pivot. If left_mark < right_mark, the values at which the marks are stopped are swaped and the process continues until they cross. At this point, a[right_mark] and the pivot are swapped and the index of the right_mark is returned.


Another divide and conquer algorithm, quick sort relies on choosing a pivot value. The list is then partitioned using the scheme described in partition_helper. This placed the pivot in its correct position in the sorted list, the function is then called on the sublist a[:right_mark - 1] and a[right_mark+1:]

src.classic_algo.sort.quicksort_helper(a, first, last)[source]

Helper function splitting the list at the pivot and recursively calling itself on the left and right parts of this splitpoint.


Swapping values can be an expensive operation. At the i-th pass, the selection sort finds the largest values and swap it with the value at n - i performing faster than bubble sort. Note this can be shortened same as above (not shown here for clarity)


Variant of the short bubble, taking advantage of the fact we know that if no value has been swaped, the list is sorted and we can return early.