Merge Sort
Merge sort is an efficient, stable, divide-and-conquer sorting algorithm that works by recursively splitting an array into two halves, sorting each half, and then merging the sorted halves back together. It guarantees a time complexity of O(n log n) in all cases — best, average, and worst — making it more predictable than quicksort. Merge sort is the preferred algorithm for sorting linked lists and is used in many standard library implementations such as Python's Timsort.
Key Formula
T(n) = 2T(n/2) + O(n)
LaTeX: T(n) = 2T\left(\frac{n}{2}\right) + O(n)
| Symbol | Meaning | Unit |
|---|---|---|
| T(n) | Time to sort n elements | operations |
| 2T(n/2) | Time to recursively sort two halves | operations |
| O(n) | Time to merge two sorted halves | operations |
Worked Example
Problem
Sort the array [38, 27, 43, 3] using merge sort.
Solution
Step 1: Split [38, 27, 43, 3] → [38, 27] and [43, 3]. Step 2: Split [38, 27] → [38] and [27]; split [43, 3] → [43] and [3]. Step 3: Merge [38] and [27] → compare 38 vs 27 → [27, 38]. Merge [43] and [3] → compare 43 vs 3 → [3, 43]. Step 4: Merge [27, 38] and [3, 43] → compare 27 vs 3 → 3; compare 27 vs 43 → 27; compare 38 vs 43 → 38; append 43 → [3, 27, 38, 43].
Answer
Sorted array: [3, 27, 38, 43].
Merge Sort Complexity and Properties
| Property | Value | Notes |
|---|---|---|
| Best Case Time | O(n log n) | Even for sorted input |
| Average Case Time | O(n log n) | Consistent performance |
| Worst Case Time | O(n log n) | Guaranteed bound |
| Space Complexity | O(n) | Requires auxiliary array |
| Stability | Stable | Maintains relative order of equal elements |
| Parallelisable | Yes | Sub-problems are independent |
Interactive Tools
Wikimedia Commons, CC BY-SA
Related Terms
Quick Sort
Quick sort is a highly efficient, in-place divide-and-conquer sorting algorithm that selects a "pivot" element and partitions the array into two sub-arrays — elements less than the pivot and elements greater than the pivot — then recursively sorts each sub-array. It achieves an average time complexity of O(n log n) and is often faster in practice than merge sort due to better cache performance and lower constant factors. Quick sort is widely used in standard library implementations, including the C++ STL and Java's Arrays.sort for primitive types.
Bubble Sort
Bubble sort is a simple comparison-based sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order; this process is repeated until the list is sorted. With each full pass, the largest unsorted element "bubbles up" to its correct position at the end of the list. Despite its O(n²) worst-case time complexity making it inefficient for large datasets, bubble sort is widely taught due to its simplicity and ease of understanding.
Time Complexity
Time complexity is a measure of the amount of time an algorithm takes to complete as a function of the size of its input, typically expressed using Big O notation. It describes how the running time grows relative to the input size, helping developers predict performance and compare algorithms. Understanding time complexity is essential for writing scalable software, especially when dealing with large datasets.
Merge sort was invented by John von Neumann in 1945 as one of the earliest examples of a divide-and-conquer algorithm, originally designed for use with early computer hardware. The algorithm was described in Donald Knuth's "The Art of Computer Programming" and has remained a staple of computer science education.