Data Structures & Algorithms

Algorithm Module — Beating the comparison barrier

What You'll Learn#

1. The Two Complexity Classes#

  ┌─────────────────────────────────────────────────────────┐
  │  O(n²)        →  Bubble, Selection, Insertion, Shell    │
  │  O(n log n)   →  Merge, Quick, Heap                    │
  └─────────────────────────────────────────────────────────┘

  If n = 10,000:
    n²       = 100,000,000  (one hundred million operations)
    n log n  ≈ 132,877      (one hundred thirty-three thousand)

  That's the difference between "runs instantly"
  and "why is my laptop crying?"

2. Searching Algorithms#

Linear Search — O(n)#

Check every item one by one. Works on any list.

def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i      # Found
    return -1

Binary Search — O(log n)#

Divide search space in half. Requires sorted array! Each comparison removes half the search space (exponential reduction).

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

3. Comparison Sorts: O(n²)#

Bubble Sort#

Repeatedly compare adjacent elements. Largest bubbles to the end.

• Comparisons: n(n - 1) / 2
• Worst Case: O(n²)
• Best Case: O(n) (already sorted)
• Stable: Yes

Selection Sort#

Find smallest element, swap with first position. Repeat.

• Exam Trap: It ALWAYS performs n(n - 1) / 2 comparisons, regardless of whether input is sorted or reverse sorted.
• Worst/Best: O(n²) always!
• Swaps: At most n.
• Stable: No.

Insertion Sort#

Build sorted left portion. Highly underrated.

• Worst Case: O(n²)
• Best Case: O(n)
• Stable: Yes
• Usage: Real systems (Java, Python) switch to insertion sort for tiny arrays (e.g., n < 47) inside Quick/Merge sort because low overhead makes it very fast in practice.

Shell Sort#

Insertion sort but jumping using gaps that shrink over time.

• Time: O(n log² n) to O(n^1.5). Unstable.

4. Comparison Sorts: O(n log n)#

Merge Sort#

Divide into halves, recursively sort, and merge back.

  Recurrence: T(n) = 2T(n/2) + O(n)
  By Master Theorem → T(n) = O(n log n)

• Time: O(n log n) Always guaranteed.
• Space: O(n) (Needs extra array!)
• Stable: Yes.

Quick Sort#

Pick a pivot, position elements less than pivot left, greater right. Recursively sort halves.

• Average Time: O(n log n)
• Worst Case: O(n²) — Happens when array is sorted AND you pick extreme pivots. (Pivot strategy is critical).
• Space: O(log n) stack space.
• Stable: No.
• Why use it? Good cache behavior makes it the fastest in actual hardware practice.

Heap Sort#

Build max-heap (O(n)). Continually pop root and heapify (O(log n)).

• Time: O(n log n) Guaranteed.
• Space: O(1) — Entirely in-place!
• Stable: No.
• Usage: Reliable, no worst-case O(n²) trap like Quick Sort, no O(n) space requirement like Merge Sort.

5. The Comparison Limit#

Stable vs Unstable Sorting:

• Stable: Equal elements keep their original relative order. (Important for multi-key database sorts).
• Stable: Insertion, Merge, Bubble.
• Unstable: Quick, Heap, Selection.

The Comparison Bound Theorem:

  No comparison-based sort can beat O(n log n) in the worst case.

Every algorithm above compares A < B. The mathematics of decision trees proves they can never be faster than O(n log n).

So, how do we go faster? We stop comparing!

6. Breaking the Barrier: Non-Comparison Sorts#

Non-comparison algorithms beat n log n time by making strict assumptions about the data.

Counting Sort#

Assumption: Elements are integers in a small range [0 ... k].

Idea:

1. Count occurrences of each value in a count[] array.
2. Convert counts to prefix sums (to determine exact final array indices).
3. Place elements directly in correct positions (working backwards to maintain stability).

  Time: O(n + k)
  Space: O(n + k)
  Stable: YES

Exam Trick: If k = O(n), then Counting Sort is strictly O(n).

Drawback: It is terrible if the range is huge. Sorting 5 phone numbers requires an array size of 9,999,999,999! Great for exam marks (0-100), bad for large ranges.

Radix Sort#

Sort digit by digit, from Least Significant Digit (LSD) up to the Most Significant Digit. Each digit pass MUST use a stable sort (like counting sort under the hood).

Idea: Why sort whole numbers when you can sort by the 1s place, then the 10s place, then 100s?

  Time: O(d(n + k))   Where 'd' is the number of digits.
  Space: O(n + k)
  Stable: YES

Real-world Example: Sorting standard dates. Day → Month → Year. By sorting year last, the stability keeps the months/days ordered! Radix is clever engineering layered on Counting Sort.

Bucket Sort#

Assumption: Input data is uniformly distributed randomly over a range (like [0, 1)).

Idea:

1. Create n empty buckets.
2. Scatter elements into buckets based on value.
3. Sort each bucket individually (often using insertion sort).
4. Concatenate the buckets.

  Average Time: O(n)
  Worst Case Time: O(n log n)  OR  O(n²)

The Trap: If the data isn't uniformly distributed, all elements might fall into a single bucket. Then Bucket Sort degrades to whatever algorithm was used to sort the individual bucket!

7. The Master Summary Table#

TL;DR - Formula Sheet#

Recurrences & Complexity:

• Merge Sort Recurrence: T(n) = 2T(n/2) + n
• Comparison Lower Bound: O(n log n)
• Counting Sort Time: O(n + k)
• Radix Sort Time: O(d(n + k))

Golden Rules:

1. Quick Sort Worst Case occurs when array is already sorted and pivot is extreme.
2. Selection Sort makes n(n-1)/2 comparisons no matter what the input is.
3. Counting Sort requires memory proportional to the maximum value (k), making it fail for huge data ranges.
4. Radix Sort MUST use a stable sorting sub-routine (like Counting Sort) to work.

Additional Resources#

Video Courses:

• Abdul Bari - Sorting Algorithms
• MIT 6.006 - Linear Sorting (Counting/Radix)

Practice Problems:

• LeetCode 912: Sort an Array
• LeetCode 75: Sort Colors (Dutch National Flag)
• LeetCode 164: Maximum Gap (Radix Sort / Bucket Sort Application)