Lesson 2: Sorting Algorithms

$O(n^2)$ vs. $O(n \log n)$ Sorts

From simple swaps to recursive partitioning. Master the algorithms that organize the world's data with surgical precision.

75 Minutes

Intermediate

The Sorting Landscape

Algorithm	Avg Time	Space	Stable
Bubble Sort	O(n^2)	O(1)	Yes
Insertion Sort	O(n^2)	O(1)	Yes
Merge Sort	O(n log n)	O(n)	Yes
Quick Sort	O(n log n)	O(log n)	No
Heap Sort	O(n log n)	O(1)	No

1. Simple Sorts: $O(n^2)$

Great for small arrays or nearly-sorted data. Insertion Sort is particularly special as it powers the "small-array" optimization in library sorts like Timsort.

Insertion Sort Logic

Like sorting cards in your hand. You take one card and "shift" larger cards until you find the right slot.

Insertion Sort Implementation

Pseudocode

1function insertionSort(arr):
2  for i from 1 to n-1:
3    key = arr[i]
4    j = i - 1
5    
6    // Shift elements
7    while j >= 0 and arr[j] > key:
8      arr[j+1] = arr[j]
9      j = j - 1
10      
11    arr[j+1] = key

2. Merge Sort

A Divide and Conquer powerhouse. It guarantees $O(n \log n)$ even in the worst case by recursively splitting and merging.

The Tradeoff

While predictable and stable, Merge Sort is not "in-place". It requires $O(N)$ extra space to store the merged sub-arrays.

Merge Logic

Pseudocode

1function merge(left, right):
2  result = []
3  while left and right exist:
4    if left[0] <= right[0]:
5      result.push(left.shift())
6    else:
7      result.push(right.shift())
8      
9  return result + left + right

3. Quick Sort

The fastest sort in practice for most systems. It uses an in-place partitioning strategy that is incredibly cache-friendly.

Pivot

Strategic center element selection.

Partition

Reordering relative to pivot.

Lomuto Partitioning

Pseudocode

1function partition(arr, low, high):
2  pivot = arr[high]
3  i = low - 1
4  
5  for j from low to high-1:
6    if arr[j] < pivot:
7      i++
8      swap(arr[i], arr[j])
9      
10  swap(arr[i+1], arr[high])
11  return i+1

4. Heap Sort

The middle ground between Merge and Quick. It guarantees $O(n \log n)$ like Merge Sort, but operates in-place like Quick Sort.

Build Max-Heap

First, reorganize the array into a binary tree where every parent is larger than its children. This takes $O(N)$ time.

The Extraction

Repeatedly swap the root (largest) with the last element and "heapify" down. Total time: $O(N \log N)$.

Which one should you use?

Nearly sorted or tiny array (N < 20)?

Use: Insertion Sort

Tiny overhead, adaptive magic.

Memory is tight and guaranteed speed needed?

Use: Heap Sort

O(1) extra space plus O(N log N).

Stability is non-negotiable?

Use: Merge Sort

Preserves original order of duplicates.

General purpose / fast as possible?

Use: Quick Sort

Most systems use Introsort (Quick + Heap hybrid).

Course Fundamentals Next: Searching Algorithms

Algorithm

Avg Time

Space

Stable

Bubble Sort

O(n^2)

O(1)

Yes

Insertion Sort

O(n^2)

O(1)

Yes

Merge Sort

O(n log n)

O(n)

Yes

Quick Sort

O(n log n)

O(log n)

Heap Sort

O(n log n)

O(1)

1function insertionSort(arr): 2 for i from 1 to n-1: 3 key = arr[i] 4 j = i - 1 5 6 // Shift elements 7 while j >= 0 and arr[j] > key: 8 arr[j+1] = arr[j] 9 j = j - 1 10 11 arr[j+1] = key

1function merge(left, right): 2 result = [] 3 while left and right exist: 4 if left[0] <= right[0]: 5 result.push(left.shift()) 6 else: 7 result.push(right.shift()) 8 9 return result + left + right

1function partition(arr, low, high): 2 pivot = arr[high] 3 i = low - 1 4 5 for j from low to high-1: 6 if arr[j] < pivot: 7 i++ 8 swap(arr[i], arr[j]) 9 10 swap(arr[i+1], arr[high]) 11 return i+1

4. Heap Sort

The middle ground between Merge and Quick. It guarantees $O(n \log n)$ like Merge Sort, but operates in-place like Quick Sort.

Build Max-Heap

First, reorganize the array into a binary tree where every parent is larger than its children. This takes $O(N)$ time.

The Extraction

Repeatedly swap the root (largest) with the last element and "heapify" down. Total time: $O(N \log N)$.

Which one should you use?

Nearly sorted or tiny array (N < 20)?

Use: Insertion Sort

Tiny overhead, adaptive magic.

Memory is tight and guaranteed speed needed?

Use: Heap Sort

O(1) extra space plus O(N log N).

Stability is non-negotiable?

Use: Merge Sort

Preserves original order of duplicates.

General purpose / fast as possible?

Use: Quick Sort

Most systems use Introsort (Quick + Heap hybrid).