Skip to main content

DSAPath8 mincore

Merge Sort

Merge sort splits an array, recursively sorts the halves, and merges the sorted halves. It gives stable O(n log n) sorting with O(n) extra space.

Why This Matters

Merge sort is the cleanest first divide-and-conquer sorting algorithm. The recurrence is simple, the correctness argument is local, and the runtime is reliably O(nlog⁡n)O(n \log n).

Core Idea

Split the input into two halves, sort each half, then merge the sorted halves in linear time.

Worked example: [4, 1, 3, 2] splits into [4, 1] and [3, 2], sorts to [1, 4] and [2, 3], then merges to [1, 2, 3, 4].

The recurrence is:

T(n)=2T(n/2)+O(n),T(n) = 2T(n/2) + O(n),

which solves to O(nlog⁡n)O(n \log n).

Common Mistakes

  • Forgetting the merge step is linear, not constant.
  • Claiming merge sort is in-place in its standard array form.
  • Using merge sort when memory budget is tighter than stability needs.

Exercises

  • Merge [1, 4, 8] and [2, 3, 9].
  • Draw the recursion tree for eight items.
  • Explain why merge sort is stable when the merge breaks ties from the left half.

Next Topics

References

  • Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (4th ed., 2022). Ch. 2.
  • MIT OpenCourseWare. 6.006 Introduction to Algorithms, Spring 2020.