Merge Sort DC
Merge sort is a classic divide-and-conquer sorting algorithm. It divides the array into halves, recursively sorts each half, then merges the two sorted halves. It guarantees O(n log n) time and is stable, but uses O(n) extra space.
Algorithm steps:
1. If array has 1 or 0 elements, it's already sorted (base).
2. Find middle index, divide into left and right halves.
3. Recursively sort left and right halves.
4. Merge the two sorted halves into a sorted whole.
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: divide, sort, merge.
- Time O(n log n) always, space O(n).
- Stable, good for linked lists and external sorting.
- Recurrence: T(n) = 2T(n/2) + O(n).
Need more clarification?
Drop us an email at career@quipoinfotech.com