← Back to DSA
🔀
Sorting
Merge Sort
A divide-and-conquer algorithm that recursively splits the array in half, sorts each half, then merges them back.
Complexity
Time (Best)
O(n log n)
Time (Avg)
O(n log n)
Time (Worst)
O(n log n)
Space
O(n)
Key Points
- ›Guaranteed O(n log n) in all cases — no worst-case degradation
- ›Stable sort: preserves relative order of equal elements
- ›Requires O(n) extra space for the merge step
- ›Preferred for sorting linked lists (no random access needed)
- ›Basis for external sorting (sorting data too large for RAM)
Interactive Visualizer
Step 0 / 0✓ Sorted!
SlowFast
DefaultComparingSwappingSorted
Code Examples
Swift
func mergeSort(_ arr: [Int]) -> [Int] {
guard arr.count > 1 else { return arr }
let mid = arr.count / 2
let left = mergeSort(Array(arr[..<mid]))
let right = mergeSort(Array(arr[mid...]))
return merge(left, right)
}
func merge(_ left: [Int], _ right: [Int]) -> [Int] {
var result = [Int]()
var i = 0, j = 0
while i < left.count && j < right.count {
if left[i] <= right[j] { result.append(left[i]); i += 1 }
else { result.append(right[j]); j += 1 }
}
return result + Array(left[i...]) + Array(right[j...])
}
print(mergeSort([38, 27, 43, 3, 9, 82, 10]))
// [3, 9, 10, 27, 38, 43, 82]