CSS Prepare

optional · CSS study notes

Merge Sort

Mechanism (Divide and Conquer)

  1. Divide: recursively split the array into halves until each sub-array has 1 element
  2. Conquer: merge sorted sub-arrays back together by repeatedly comparing front elements

Pseudocode

MERGE_SORT(arr, low, high):
  IF low < high:
    mid = (low + high) / 2
    MERGE_SORT(arr, low, mid)
    MERGE_SORT(arr, mid+1, high)
    MERGE(arr, low, mid, high)

Complexity

  • Time: O(n log n) in ALL cases (best, average, worst) — unlike Quick Sort, performance doesn't degrade
  • Space: O(n) — requires auxiliary array for merging (not in-place) — key weakness vs Quick Sort/Heap Sort
  • Stable sort (preserves relative order of equal elements)

Exam Angle / MCQ Trap

Merge Sort's guaranteed O(n log n) worst-case makes it preferred for linked lists (no random access penalty) and for external sorting (large datasets that don't fit in memory). Its O(n) space cost is the classic trade-off point examiners test against Quick Sort's O(log n) space but O(n²) worst case.

📌 Sample & Repeated FPSC Questions (2016–2026)

2026, Paper I, Q5(b) (6 marks) — What is the difference between Time Complexity and Space Complexity? Explain with examples.

Time complexity measures how the number of basic operations grows with input size n (asymptotic, hardware-independent). Space complexity measures how much extra working memory (beyond the input) an algorithm needs as a function of n.

Key reasoning points:

  • Merge Sort is the standard example of the trade-off: time complexity O(n log n), but space complexity O(n) — because it needs a full auxiliary array to merge sorted halves back together. This is exactly why this page's Exam Angle box calls Merge Sort's O(n) space its "key weakness vs Quick Sort/Heap Sort."
  • Contrast: Linear Search is O(n) time / O(1) space (fast-ish, memory-light); Merge Sort is O(n log n) time / O(n) space (fast, memory-hungry) — a good algorithm can be fast but not memory-light, and vice versa (e.g. naive recursive Fibonacci is O(2ⁿ) time but only O(n) space).