45-Minute Sorting Algorithms Mastery Guide
SORTING CONCEPTS (5 mins)
Sorting Concept
Definition: Arranging data elements in a specific order (ascending/descending) according to a key
field.
Order (Time Complexity)
Definition: Efficiency classification of sorting algorithms.
O(n²): Elementary sorts (Bubble, Insertion, Selection)
O(n log n): Advanced sorts (Merge, Quick, Heap)
O(n): Linear sorts (Counting, Radix - special cases)
Memorable: "Elementary is squared, Advanced logs the n"
Stability
Definition: A sort is stable if equal elements maintain their relative order from the original array.
Stable: Insertion, Merge, Bubble
Unstable: Quick, Heap, Selection
Example: [5a, 3, 5b] → sorted → [3, 5a, 5b] = STABLE; [3, 5b, 5a] = UNSTABLE
Memorable: "If twins stay in order, it's STABLE"
SELECTION SORTS (8 mins)
Straight Selection Sort
Definition: Repeatedly finds minimum element and places it at front.
Algorithm:
FOR i = 0 to n-2:
minIndex = i
FOR j = i+1 to n-1:
IF array[j] < array[minIndex]:
minIndex = j
SWAP array[i] with array[minIndex]
Memorable: "Find minimum, swap to front, repeat"
Time: O(n²) | Space: O(1) | Stable: NO
Example: [64, 34, 25, 12] → [12, 34, 25, 64] → [12, 25, 34, 64]
Heap Sort
Definition: Uses max-heap structure to sort by repeatedly extracting maximum element.
Algorithm:
1. Build Max-Heap from array
2. FOR i = n-1 to 1:
SWAP array[0] with array[i] (move max to end)
HEAPIFY from root with reduced heap size
Memorable: "Build heap mountain, pick peaks from top"
Time: O(n log n) | Space: O(1) | Stable: NO
Binary Heap Property: Parent ≥ Children (max-heap)
Key Insight: Complete binary tree in array format where parent at index i has children at 2i+1 and
2i+2
INSERTION SORTS (8 mins)
Straight Insertion Sort
Definition: Builds sorted array by inserting each element into its correct position.
Algorithm:
FOR i = 1 to n-1:
key = array[i]
j = i - 1
WHILE j ≥ 0 AND array[j] > key:
array[j+1] = array[j]
j = j - 1
array[j+1] = key
Memorable: "Pick card, compare left, shift right, insert"
Time: O(n²) worst, O(n) best | Space: O(1) | Stable: YES
Best Case: Already sorted array
Worst Case: Reverse sorted array
Shell Sort (Diminishing Increment Sort)
Definition: Generalization of insertion sort using gap sequence; sorts sublists with decreasing gaps.
Algorithm:
gap = n/2
WHILE gap > 0:
FOR i = gap to n-1:
key = array[i]
j = i - gap
WHILE j ≥ 0 AND array[j] > key:
array[j + gap] = array[j]
j = j - gap
array[j + gap] = key
gap = gap/2
Memorable: "Divide by 2 gaps, insertion sort each, repeat until gap=1"
Time: O(n^1.3) to O(n log² n) | Space: O(1) | Stable: NO
Gap Sequences: Knuth: (3k+1), Hibbard: (2^k-1)
Key Insight: Partially sorts array first; final pass is fast insertion sort
EXCHANGE SORTS (12 mins)
Bubble Sort
Definition: Repeatedly swaps adjacent elements if they're in wrong order; largest element "bubbles"
to end.
Algorithm:
FOR i = 0 to n-1:
swapped = FALSE
FOR j = 0 to n-i-2:
IF array[j] > array[j+1]:
SWAP array[j] with array[j+1]
swapped = TRUE
IF NOT swapped:
BREAK (optimization: early exit if sorted)
Memorable: "Compare neighbors, bubble heavy to end"
Time: O(n²) | Space: O(1) | Stable: YES
Optimized: O(n) best case with early exit
Passes: n-1 passes needed for worst case
Quick Sort
Definition: Divide-and-conquer: partition around pivot, recursively sort partitions.
Algorithm:
QUICKSORT(array, low, high):
IF low < high:
p = PARTITION(array, low, high)
QUICKSORT(array, low, p-1)
QUICKSORT(array, p+1, high)
PARTITION(array, low, high):
pivot = array[high]
i = low - 1
FOR j = low to high-1:
IF array[j] < pivot:
i = i + 1
SWAP array[i] with array[j]
SWAP array[i+1] with array[high]
RETURN i + 1
Memorable: "Pick pivot, elements left smaller right larger, divide & conquer"
Time: O(n log n) avg, O(n²) worst | Space: O(log n) recursive | Stable: NO
Worst case: Pivot always at extreme (sorted array, bad pivot choice)
Best case: Pivot always middle element
Pivot Strategies: Last element, first element, median-of-three, random
Key Insight: In-place, fast average, worst case unlikely with good pivot choice
MERGE SORT & EXTERNAL SORTING (12 mins)
Merge Sort (Internal Sorting)
Definition: Divide-and-conquer: divide array in half, sort each, merge sorted halves.
Algorithm:
MERGESORT(array, left, right):
IF left < right:
mid = (left + right) / 2
MERGESORT(array, left, mid)
MERGESORT(array, mid+1, right)
MERGE(array, left, mid, right)
MERGE(array, left, mid, right):
Copy left portion to temp array L
Copy right portion to temp array R
i = 0, j = 0, k = left
WHILE i < len(L) AND j < len(R):
IF L[i] ≤ R[j]:
array[k] = L[i++]
ELSE:
array[k] = R[j++]
k++
Copy remaining L or R to array
Memorable: "Divide in half, conquer each half, merge sorted halves"
Time: O(n log n) guaranteed | Space: O(n) | Stable: YES
Passes: log n levels, each level processes n elements
External Sorting (File-Based Sorting)
Concept: Sort data too large for RAM; use disk storage with multiple passes.
Natural Merge Sort
Definition: Merge existing runs (sorted subsequences) in file; run length grows each pass.
Algorithm:
Pass 1: Identify natural runs (already sorted sequences in input)
Pass 2: Merge pairs of runs (2 runs → 1 larger run)
Pass 3: Merge pairs (now 1 run or 2 larger runs)
Continue until single run remains
Memorable: "Find natural sorted chunks, merge pairs, repeat"
Example:
Input: [5,10|3,7,8|2,4,9] (3 runs: [5,10], [3,7,8], [2,4,9])
Pass 1: [3,5,7,8,10|2,4,9] (merge first two runs)
Pass 2: [2,3,4,5,7,8,9,10] (merge resulting runs)
Advantage: Fewer passes if input has long natural runs
Disadvantage: Variable pass count; difficult to optimize
Balanced Merge Sort
Definition: Fixed number of tapes/files; split input evenly, perform balanced merges each pass.
Algorithm:
Split Phase: Divide input into k tapes evenly
Merge Phase (repeat until 1 tape):
Read block from each input tape
Merge and write to output tape
When one input exhausted, fill with next
Write full output tape
Rotate tapes (output becomes input)
Memorable: "Even split, balanced merge, predictable passes"
Example (2-way merge with 3 tapes):
Tapes: T1: [5,10,3,7] | T2: [8,2,4,9] | T3: empty
Pass 1: T1: empty | T2: empty | T3: [2,3,4,5,7,8,9,10]
Result: 1 sorted file on T3
Passes: ⌈log_k(n)⌉ where k = number of input tapes
Balanced: k-way merge = k input files + 1 output
Polyphase Merge
Definition: Unbalanced merge strategy; uses all tapes in cascade, minimizes I/O passes.
Algorithm:
Initial: Distribute initial runs among k tapes unequally
Each pass: Read from k-1 input tapes, write to 1 output tape
Rotated: Output becomes new input for next iteration
Continue until all data on one tape
Memorable: "Cascade merge, rotate tapes, fewer expensive passes"
Example (3-way polyphase, initial runs):
T1: 3 runs | T2: 2 runs | T3: 1 run | T4: empty
Pass 1: Merge from T1,T2,T3 → output to T4
T1: empty | T2: empty | T3: 1 run | T4: 1 run
Pass 2: Merge from T3,T4 → output to T1,T2
Continue until sorted
Fibonacci Connection: Optimal initial distribution follows Fibonacci sequence
For 3 tapes: 2,1,0 or 3,2,0 initial run counts
Advantage: Minimizes passes (fewer than balanced merge)
Disadvantage: Complex implementation, uneven tape usage
QUICK COMPARISON CHART
Algorithm Time (Avg) Time (Worst) Space Stable Best For
Bubble O(n²) O(n²) O(1) YES Teaching, nearly sorted
Selection O(n²) O(n²) O(1) NO Minimal swaps needed
Insertion O(n²) O(n²) O(1) YES Small/nearly sorted
Shell O(n^1.3) O(n²) O(1) NO General purpose, gap tuning
Heap O(n log n) O(n log n) O(1) NO Guaranteed time
Quick O(n log n) O(n²) O(log n) NO Fast average, pivot matters
Merge O(n log n) O(n log n) O(n) YES Stable guaranteed time
Natural Merge Varies O(n log n) O(n) YES Pre-sorted data
Balanced Merge O(n log n) O(n log n) O(n) YES Predictable external sort
Polyphase Merge O(n log n) O(n log n) O(n) YES Minimize I/O operations
MEMORY MNEMONICS
Elementary Sorts (O(n²)): "BIS" = Bubble, Insertion, Selection
Advanced Sorts (O(n log n)): "HQMB" = Heap, Quick, Merge, (Balanced/Blended)
Stable: "BIM" = Bubble, Insertion, Merge (also Natural Merge, Balanced Merge)
In-Place: "BISH" = Bubble, Insertion, Selection, Heap (and Quick mostly)
External Sort Types: "NBP" = Natural, Balanced, Polyphase
45-MINUTE STUDY SCHEDULE
0-5 min: Sorting Concepts (definition, order, stability)
5-13 min: Selection Sorts (Straight + Heap)
13-21 min: Insertion Sorts (Straight + Shell)
21-33 min: Exchange Sorts (Bubble + Quick) - allocate more time for Quick
33-45 min: Merge Sort + External Sorting (merge, natural, balanced, polyphase)
Practice writing pseudocode for each algorithm without reference!