Loading...
Merge Sort is a divide-and-conquer algorithm: it recursively splits the array in half, sorts each half, and merges them back in linear time. It guarantees O(n log n) in all cases and is stable, which makes it a common choice for sorting linked lists and external (on-disk) data.
Splits the array, sorts each half, then merges the sorted halves.
| Best case | O(n log n) |
| Average case | O(n log n) |
| Worst case | O(n log n) |
| Space | O(n) |
| Stable | Yes |
Complexities are for the reference implementation shown; constant factors and cache behavior vary by language.
Idiomatic, copy-paste implementations. Pick your language:
Python
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
result.extend(left[i:])
result.extend(right[j:])
return resultSorting [5, 1, 4, 2] step by step:
The control flow of the algorithm as a diagram: