Merge Sort

Merge Sort is a comparison-based sorting algorithm that also follows the Divide and Conquer approach. It works by dividing the array into two halves, recursively sorting each half, and then merging the two sorted halves back together into a single sorted array.

Merge Sort guarantees O(n log n) time complexity in all cases (best, average, and worst), making it one of the most reliable sorting algorithms — especially valuable when consistent performance matters.

How Merge Sort Works?

  1. Divide: Split the array into two halves at the middle index.
  2. Conquer: Recursively sort each half by applying Merge Sort to it.
  3. Combine: Merge the two sorted halves into one sorted array by repeatedly comparing the smallest remaining elements of each half.
  4. The recursion stops when a sub-array has only 0 or 1 element (already sorted by definition).

Example: Sorting [38, 27, 43, 3, 9, 82, 10]

Initial array: [38, 27, 43, 3, 9, 82, 10]

Divide step:

  • Split into [38, 27, 43] and [3, 9, 82, 10]
  • Split further: [38, 27, 43] → [38] and [27, 43] → [27], [43]
  • [3, 9, 82, 10] → [3, 9] and [82, 10] → [3], [9], [82], [10]

Conquer & Merge step (bottom-up):

  • Merge [27] and [43] → [27, 43]
  • Merge [38] and [27, 43] → [27, 38, 43]
  • Merge [3] and [9] → [3, 9]
  • Merge [82] and [10] → [10, 82]
  • Merge [3, 9] and [10, 82] → [3, 9, 10, 82]

Final merge:

  • Merge [27, 38, 43] and [3, 9, 10, 82]:
    • Compare 27 & 3 → take 3
    • Compare 27 & 9 → take 9
    • Compare 27 & 10 → take 10
    • Compare 27 & 82 → take 27
    • Compare 38 & 82 → take 38
    • Compare 43 & 82 → take 43
    • Remaining: take 82
    • Result: [3, 9, 10, 27, 38, 43, 82]

Final Sorted Array: [3, 9, 10, 27, 38, 43, 82]

Merge stepLeftRightMerged Result
1[27][43][27, 43]
2[38][27, 43][27, 38, 43]
3[3][9][3, 9]
4[82][10][10, 82]
5[3, 9][10, 82][3, 9, 10, 82]
6[27, 38, 43][3, 9, 10, 82][3, 9, 10, 27, 38, 43, 82]

Pseudocode

Step 1: Start
Step 2: Function mergeSort(array, low, high):
Step 3:     If low < high:
Step 4:         mid = (low + high) / 2
Step 5:         mergeSort(array, low, mid)
Step 6:         mergeSort(array, mid + 1, high)
Step 7:         merge(array, low, mid, high)

Step 8: Function merge(array, low, mid, high):
Step 9:     Create temporary arrays Left and Right from array[low..mid] and array[mid+1..high]
Step 10:    Compare elements of Left and Right one by one,
                placing the smaller element back into array in order
Step 11:    Copy any remaining elements from Left or Right into array
Step 12: End

Advantages

  • Guaranteed O(n log n) performance in best, average, and worst case very predictable.
  • Stable sort equal elements retain their relative order.
  • Well suited for sorting linked lists (no random access needed for merging).
  • Works well for external sorting (sorting data too large to fit in memory, e.g., sorting large files on disk).
  • Easily parallelizable, since the two halves can be sorted independently.

Disadvantages

  • Requires O(n) extra space for the temporary arrays used during merging not in-place.
  • Slower than Quick Sort in practice for small arrays, due to overhead of recursive calls and extra memory allocation.
  • Copying data between temporary and original arrays adds overhead.

Time and Space Complexity

CaseTime ComplexityExplanation
Best CaseO(n log n)Array is always split into halves and merged regardless of initial order
Average CaseO(n log n)Same divide-and-merge process applies
Worst CaseO(n log n)Performance does not degrade based on input order

Space Complexity: O(n) extra arrays are required during the merge step.

Stability: Stable In-place: No (requires auxiliary space)

When to Use Merge Sort?

  • When stability is required.
  • When working with linked lists, where merging is efficient without random access.
  • When sorting large datasets from external storage (external sorting).
  • When consistent, predictable O(n log n) performance is more important than average-case speed or memory usage.

Practice Questions

  1. Sort the array [12, 11, 13, 5, 6, 7] using Merge Sort. Show the divide steps and the merge steps separately.
  2. Trace the recursive division of the array [8, 4, 2, 9, 1, 6, 3, 5] down to single-element sub-arrays.
  3. Merge the two sorted sub-arrays [2, 6, 9] and [1, 3, 8] manually, showing every comparison made.
  4. Explain, with a short example, why Merge Sort is described as a "stable" sorting algorithm.
  5. Why does Merge Sort require O(n) additional space? Explain using an example array of 6 elements.
  6. Compare Merge Sort and Quick Sort in terms of worst-case time complexity and typical use cases.
  7. For the array [19, 7, 13, 25, 2, 30, 15], write out the final merge step showing all comparisons in the last merge.
  8. Write a program to implement Merge Sort recursively and test it on an array of 12 elements.
  9. Explain why Merge Sort is a good choice for sorting a large file stored on disk that cannot fit into memory.
  10. Given the array [100, 50, 75, 25, 90, 10], manually perform Merge Sort and list the sub-arrays formed at each level of recursion.
Previous Post
Quick Sort
Next Post
Shell Sort
0 people found this article helpful

Was this article helpful?