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.
text
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.
Applications: You use Merge Sort for external sorting (large files), linked list sorting, counting inversions, and stable sorting requirements.
Time complexity: in all cases.
Space complexity: for the temporary array during merging.