Sorting

Merge Sort

A stable divide-and-conquer sorting algorithm that recursively splits and merges sub-arrays.

What is Merge Sort?

Merge Sort is an O(N log N) comparison-based sorting algorithm. It is a divide-and-conquer algorithm that recursively divides the input array into two halves, calls Merge Sort on each half, and then merges the two sorted halves back together into a single sorted array.

Key Characteristics:

  • Divide-and-conquer design.
  • Stable sorting algorithm.
  • Not in-place: requires O(N) auxiliary space for temp arrays.
  • Guaranteed O(N log N) performance regardless of initial array ordering.

Complexity Analysis

Avg Time Complexity: O(N * log N) for all cases
Space Complexity: O(N) auxiliary space
Best Case: O(N * log N)
Worst Case: O(N * log N)

How it Works Step-by-Step

  1. Divide: Calculate midpoint: mid = (low + high) / 2.
  2. Sort Partitions: Recursively call Merge Sort on the left half (low to mid) and right half (mid+1 to high).
  3. Merge Temp: Combine the two sorted halves by comparing elements from each, copying them in sorted order into a temporary array.
  4. Update Source: Copy the merged values from the temporary array back to the original array.

Code Implementation

Worked Trace Example

Sorting [38, 27, 43, 3]:
1. Split into left [38, 27] and right [43, 3].
2. Split [38, 27] into [38] and [27]. Merge them back sorted -> [27, 38].
3. Split [43, 3] into [43] and [3]. Merge them back sorted -> [3, 43].
4. Merge [27, 38] and [3, 43]: compare 27,3 (add 3) -> compare 27,43 (add 27) -> compare 38,43 (add 38) -> add 43.
Result: Sorted array [3, 27, 38, 43].

Ready to Understand Merge Sort Visually?

Don't just read about it. Launch our interactive, premium algorithm visualizer to step through calculations in real-time.

Launch Merge Sort Visualizer →