Merge Sort
Merge Sort is more advanced, divide-and-conquer algorithm that recursively splits an unsorted list into smaller sublists until each contains a single element. These sublists are then merged back together in a sorted manner. With a time complexity of O(n log n), Merge Sort is efficient and stable, making it suitable for handling large datasets.
Pseudocode
function mergeSort(start, end):
if start < end:
mid = (start + end) / 2
mergeSort(start, mid)
mergeSort(mid + 1, end)
merge(start, mid, end)
Visualizer
Select number of elements:
How It Works
Merge Sort follows the divide-and-conquer paradigm. It begins by dividing the input array in half, then recursively divides each half until every sub-array contains just one element (which is trivially sorted). The "conquer" phase then merges pairs of sorted sub-arrays back together. During each merge operation, two sorted sub-arrays are combined by comparing their elements one at a time: the smaller element is placed first into a temporary array. The temporary array then overwrites the corresponding section of the original array. This bottom-up merging continues until the entire array is reconstructed in sorted order.
When to Use
Merge Sort is the preferred choice when a guaranteed O(n log n) worst-case performance is required, or when stability is important. It is commonly used for sorting linked lists (where its O(n) space overhead does not apply) and for external sorting when data is too large to fit in memory. Python's built-in Timsort algorithm is a hybrid of Merge Sort and Insertion Sort, combining the best properties of both approaches.
Time & Space Complexity
Metric / Operation | Complexity | Description |
|---|---|---|
| Best Case | O(n log n) | Merge Sort always divides and merges, regardless of the initial order of elements. |
| Average Case | O(n log n) | The divide-and-merge process is consistent across all inputs. |
| Worst Case | O(n log n) | Unlike Quick Sort, Merge Sort guarantees O(n log n) even in the worst case. |
| Space Complexity | O(n) | Merge Sort requires additional memory for the temporary arrays used during merging, making it not in-place. |
💬 Discussion
Sign in to join the discussion
Curious to Learn More?
Hand-picked resources to deepen your understanding
© 2025 See Algorithms. Code licensed under MIT, content under CC BY-NC 4.0.