Merge Sort is a classic divide-and-conquer algorithm. It recursively splits the array into halves until each piece has one element, then merges those pieces back in sorted order. It guarantees O(n log n) performance in all cases and is stable, making it the preferred sort for linked lists and external sorting.
void merge(vector<int>& arr, int l, int m, int r) {
vector<int> left(arr.begin()+l, arr.begin()+m+1);
vector<int> right(arr.begin()+m+1, arr.begin()+r+1);
int i=0, j=0, k=l;
while (i<left.size() && j<right.size())
arr[k++] = (left[i]<=right[j]) ? left[i++] : right[j++];
while (i<left.size()) arr[k++]=left[i++];
while (j<right.size()) arr[k++]=right[j++];
}
void mergeSort(vector<int>& arr, int l, int r) {
if (l < r) {
int m = l + (r-l)/2;
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}Merge Sort splits the array in half repeatedly until each subarray has one element (which is trivially sorted). It then merges pairs of sorted subarrays back together, building up to the full sorted array.
Merging two sorted arrays takes O(n) time. We use two pointers, one into each half, always appending the smaller element. This is the core operation that does the actual sorting.
Merge Sort is stable because equal elements from the left half are always placed before equal elements from the right half during the merge step.
Merge Sort requires O(n) auxiliary space for the temporary arrays used during merging. This is its main disadvantage versus in-place sorts like Quick Sort.
Merge Sort is ideal for external sorting (data too large for RAM) because it accesses data sequentially. It is also preferred for sorting linked lists since random access is not needed.
Merge Sort follows which paradigm?
What is the space complexity of standard Merge Sort?
Merge Sort is preferred over Quick Sort when: