Name Time Complexity Sapce Complexity
Bubble Sort O(n^2) O(1)
Selection Sort O(n^2) O(1)
Insertion Sort O(n^2) O(1)
Merge Sort O(n log(n)) O(n)
Quick Sort O(n^2) O(log(n))
Heap Sort O(n log(n)) O(1)
Counting Sort O(n+k) O(k)
Radix Sort O(nk) O(n+k)

Bubble Sort

1
2
3
4
5
6
def bubbleSort(ls):
    for i in range(len(ls) - 1):
        for j in range(len(ls) - 1  - i):
            if ls[j] > ls[j + 1]:
                ls[j], ls[j+1] = ls[j+1], ls[j]
    return ls

Selection Sort

1
2
3
4
5
6
7
8
def selectSort(ls):
    for i in range(len(ls)):
        mini = i
        for j in range(i + 1, len(ls)):
            if ls[j] < ls[mini]:
                mini = j
            ls[mini], ls[i] = ls[i], ls[mini]
    return ls

Insertion Sort

1
2
3
4
5
6
7
def insertSort(ls):
    for i in range(1, len(ls)):
        for j in range(i, 0, -1):
            if ls[j] >= ls[j - 1]:
                break
            ls[j], ls[j - 1] = ls[j - 1], ls[j]
    return ls

Merge Sort

An divide and conquer approch.

  1. If the list is of length 0 or 1, then it is already sorted. Otherwise:
  2. Divide the unsorted list into two sublists of about half the size.
  3. Sort each sublist recursively by re-applying merge sort.
  4. Merge the two sublists back into one sorted list.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def merge(arr1, arr2):
    res = []
    while arr1 and arr2:
        if arr1[0] <= arr2[0]:
            res.append(arr1.pop(0))
        else:
            res.append(arr2.pop(0))
        res += arr1 if arr1 else arr2
    return res

def mergeSort(arr):
    if len(arr) < 2:
        return arr
    left = arr[:len(arr) // 2]
    right = arr[len(arr) // 2:]
    return merge(mergeSort(left), mergeSort(right))

Quick Sort

An divide and conquer strategy. Select a pivot. elements less than pivot, move to the left side, else move to the right side.
set the first element as pivot
Sort in place:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def partition(arr, left, right):
    pivot = arr[right]
    i = left - 1
    for j in range(left, right):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[right] = arr[right], arr[i+1]
    return i + 1

def quickSort(arr, left, right):
    if left < right:
        q = partition(arr, left, right)
        quickSort(arr, left, q - 1)
        quickSort(arr, q + 1, right)

Heap Sort

Heapq Module
About Heap Sort

  1. Build a max heap
  2. replace the root (current largest number) with the last item and reduce the heap size by 1. At this time, the largerst number is sorted and excluded from the heap.
  3. repeat step 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def heapify(arr, n, i):
    largest = i  # Initialize largest as root
    l = 2 * i + 1
    r = 2 * i + 2
 
    # check if any child is greater than root
    if l < n and arr[largest] < arr[l]:
        largest = l
    if r < n and arr[largest] < arr[r]:
        largest = r
 
    # if child greater than node, bubble it up.
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # swap
 
        # Heapify the root.
        heapify(arr, n, largest)
 
 
def heapSort(arr):
    n = len(arr)
 
    # Build a maxheap.
    for i in reversed(range(n // 2)):
        heapify(arr, n, i)
 
    # get sorted items one by one
    for i in reversed(range(1, n)):
        arr[i], arr[0] = arr[0], arr[i]  # swap
        heapify(arr, i, 0)

Counting Sort