Topic 50 of 78
Merge Sort
Overview
Merge Sort is a legendary 'Divide and Conquer' algorithm. It mathematically guarantees an O(N log N) time complexity, making it incredibly reliable for massive datasets. It works by recursively splitting an array in half until you have single elements, and then 'merging' those sorted halves back together. It is the gold standard when you need a Stable sort that guarantees performance.
Syntax
Splitting the array takes O(log N) depth. Merging them back together touches every element O(N). Result: O(N log N).
The Merge Sort Algorithm
java
public void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
// 1. Divide
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// 2. Conquer (Merge)
merge(arr, left, mid, right);
}
}
public void merge(int[] arr, int left, int mid, int right) {
// Create temporary arrays for left and right halves
int n1 = mid - left + 1;
int n2 = right - mid;
int[] L = new int[n1];
int[] R = new int[n2];
// Copy data
for (int i = 0; i < n1; ++i) L[i] = arr[left + i];
for (int j = 0; j < n2; ++j) R[j] = arr[mid + 1 + j];
// Merge the temp arrays back into arr
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) arr[k++] = L[i++];
else arr[k++] = R[j++];
}
// Copy remaining elements
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}Common Pitfalls
- Forgetting the O(N) space complexity. If you are sorting 10GB of data, Merge Sort requires another 10GB of RAM to run.
- Implementing the merge logic incorrectly, particularly failing to copy over the remaining elements if one array empties before the other.
Interview Tips
- Merge Sort requires O(N) auxiliary space to hold the temporary arrays during the merge step. This is its biggest drawback compared to Quick Sort.
Real-World Example
When sorting complex Java Objects (like a list of Employees sorted by Salary), Java uses Merge Sort (TimSort) to ensure that if two Employees have the same salary, their original alphabetical order isn't randomized.
example
java
// Collections.sort() uses TimSort (a hybrid of Merge Sort and Insertion Sort)
List<Employee> list = new ArrayList<>();
Collections.sort(list, (e1, e2) -> e1.salary - e2.salary);