Sorting Algorithms

Insertion Sort

Vanilla Insertion Sort

f}oriibny=se"1rp,tai2Ar,[wii3]s,einstw.oa,pssno"{rtdeodwnartroaythAe[0c:oir-r1e]ctposition

This above version has $\theta(n)$ steps and each step has $\theta(n)$ comparisons. So this version of the algorithm is $\theta(n^2)$ runtime complexity.

Binary Insertion Sort

This improved version is slightly improved by using Binary Search while searching for the position to place the key A[i] in the sorted part of the array (i.e. A[0:i-1])

f}oriibny=se"1rB,tin2Aa,[riy3],Sienatr.oc,hs"no{rdtoewdnatroratyheA[c0o:rir-e1c]tposition

This above version has $\theta(n)$ steps and each step has $\theta(\log n)$ comparisons. So this version of the algorithm has $\theta(n \log n)$ comparisons; but $\theta(n^2)$ swaps. So, overall complexity is still $\theta(n^2)$

Merge Sort

mergeie_flssolere:LRrtne((==tAAu))mmr:een<rrggm2eee:__rssgrooeerr(tttLu((,rAAn[[R0n)A:/n2/:2n]]))

Time Complexity: $T(n) = c_1 + 2T(n/2) + cn$

By Master’s Theorem: $T(n) = \theta(n \log n)$

Space Complexity: $\theta(n)$ auxiliary space

Heap Sort

  • The HEAP is an implementation of the abstract data-type called priority queue
  • An array visualized as a nearly complete Binary-Tree

Heap properties:

  • parent(i) = i / 2
  • left_child(i) = 2 * i
  • right_child(i) = 2 * i + 1

Max-Heap Property:

For every node i (other than the root): A[parent(i)] >= A[i]

Build Max Heap

def build_max_heap(A):
    n = len(A)
    for i in range(n//2, -1, -1):
        max_heapify(A, i)

def max_heapify(A, i):
    l = 2*i + 1
    r = 2*i + 2
    largest = i
    if l < len(A) and A[l] > A[largest]:
        largest = l
    if r < len(A) and A[r] > A[largest]:
        largest = r
    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        max_heapify(A, largest)