Learn
Merge Sort
Merge Sort is a divide-and-conquer sorting algorithm that splits the array in half, recursively sorts each half, then merges the sorted halves. It guarantees time in all cases.
In the merge step, you combine two sorted arrays into one sorted array in linear time.
function mergeSort(arr, left, right):
if left >= right:
return
mid = (left + right) / 2
mergeSort(arr, left, mid)
mergeSort(arr, mid + 1, right)
merge(arr, left, mid, right)
function merge(arr, left, mid, right):
temp = empty array
i = left
j = mid + 1
while i <= mid and j <= right:
if arr[i] <= arr[j]:
temp.append(arr[i])
i = i + 1
else:
temp.append(arr[j])
j = j + 1
while i <= mid:
temp.append(arr[i])
i = i + 1
while j <= right:
temp.append(arr[j])
j = j + 1
copy temp back to arr[left..right]
Stability: Merge Sort is stable. Equal elements maintain their relative order. You'll use this when sorting objects by multiple keys.
Why : You divide the array times, and each level requires work for merging.