Merge Sort
Merge sort is a divide-and-conquer algorithm that splits the array into halves, recursively sorts each half, and then merges them. It guarantees O(n log n) time in all cases. It is stable but requires O(n) extra space.
Java implementation:
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
private static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int[] L = new int[n1];
int[] R = new int[n2];
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];
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++];
}
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
Two Minute Drill
- Merge sort uses divide-and-conquer; O(n log n) always.
- Stable, not in-place (needs O(n) extra space).
- Excellent for linked lists and large datasets.
- Used in external sorting when data doesn't fit in memory.
Need more clarification?
Drop us an email at career@quipoinfotech.com