Stable sorting algorithm do not reorder equal elements

Quicksort is likely faster than merge sort in practice Merge sort divides the set into the smallest possible groups then reconstructs as it sorts the grouping Quicksort continually divides the set by the average until the set is recursively sorted

If you have to sort a 50 GB list but you only have 4 GB RAM available, merge sort is better than quicksort

Insertion Sort

Worst Case: \(O(n^2)\) comparisons and swaps Best Case: \(O(n)\) comparisons, \(O(1)\) swaps Average Case: \(O(n^2)\) comparisons and swaps, \(\theta(n^2)\)

similar to sorting playing cards

can be used when the number of elements is small or when the input array is almost sorted

  1. iterate from index 1 to n
  2. compare current to its predecessor
  3. if current is smaller than predecessor, then compare it to the element before
  4. move the greater element one position up to make space

in-place sorting stable

for i in range(1, len(arr)):
    key = arr[i]
    j = i - 1
        
    while j >= 0 and key < arr[j]:
        arr[j+1] = arr[j]
        j -= 1
        
    arr[j+1] = key

Selection Sort

Merge Sort

Worst Case: O(n log n) Best Case: O(n) Average Case: O(n log n)

merge sort T(n) = 2T(n) + cn if three piles, then T(n) = 3T(n/3) + cn

A basic comparison based sorting algorithm Merge sort divides the object to be sorted into groups of at most 2 Compares each number one at a time, moving the smallest number to the left of the pair Once all pairs are sorted, it then compares left most elements of the two leftmost pairs creating a sorted group of four with the smallest numbers on the left and the largest ones on the right This process is repeated until there is only one set

Merge sort can work on streams

Quicksort

Worst Case: O(n^2) Best Case: O(n) Average Case: O(n log n)

A comparison based sorting algorithm Divides entire dataset in half by selecting the middle element and putting all smaller elements to the left of the element and larger ones to the right It repeats this process on the left side until it is comparing only two elements at which point the left side is sorted When the left side is finished sorting, it performs the same operation on the right side

Heapsort

Shell Sort

Bubble Sort

Worst Case: \(O(n^2)\) Best Case: \(O(n)\) Average Case: \(O(n^2)\)

A basic teaching comparison based sorting algorithm It iterates left to right comparing every couplet It repeats this process until it no longer moves an element to the left

in-place sorting stable

n = len(arr)

for i in range(n):
    for j in range(0, n-i-1):
        if arr[j] > arr[j+1]:
            arr[j], arr[j+1] = arr[j+1], arr[j]

Exercises

  • Implement selection sort.
  • Implement merge sort.
  • Implement quick sort.