Merge Sort
28 Jun 2014Merge sort is another comparison based sort algorithm. It closely follows divide-and-conquer paradigm, and provides \( O(nlgn) \) run time complexity in worst and average cases, however, \( O(n) \) in space complexity. Merge sort can be used for sorting huge data sets that can not fit into memory. It is also a stable sort which preserves the order of equal elements.
Algorithm
Merge sort follows a divide-and-conquer algorithm by the following steps;
- Divide : Divide the n-element sequence into two subsequences of n/2 elements each
- Conquer : Sort the two subsequences recursively using merge sort.
- Combine : Merge the two sorted subsequences to produce the sorted answer.
Complexity Analysis
Time | Space | ||
---|---|---|---|
Best case | Worst case | Average case | Worst case |
\(O(nlgn)\) | \(O(nlgn)\) | \(O(nlgn)\) | \(O(n) auxiliary\) |
Code
mergeSort procedure divides input into two equal parts by recursion until input size becomes 1. Then, merge procedure sorts and combine divided parts. The code of mergeSort procedure is as following ;
public void mergeSort(int[] numbers, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
// divide array into two equal parts
mergeSort(numbers, left, mid);
mergeSort(numbers, mid + 1, right);
// merge part
merge(numbers, left, mid, right);
}
}
merge procedure is the part where subarrays are combined and sorted. Thus, merge procedure on an n-element subarray takes time \( O(n) \). Code of merge procedure is as follows;
private void merge(int[] numbers, int left, int mid, int right) {
int[] leftArray = new int[mid - left + 1];
int[] rightArray = new int[right - mid];
// copy values into created arrays
System.arraycopy(numbers, left, leftArray, 0, leftArray.length);
System.arraycopy(numbers, mid + 1, rightArray, 0, rightArray.length);
int leftIndex = 0;
int rightIndex = 0;
int k = left;
while (leftIndex < leftArray.length && rightIndex < rightArray.length) {
if (leftArray[leftIndex] <= rightArray[rightIndex]) {
numbers[k] = leftArray[leftIndex];
leftIndex++;
} else {
numbers[k] = rightArray[rightIndex];
rightIndex++;
}
k++;
}
// copy rest of the left array
while (leftIndex < leftArray.length) {
numbers[k] = leftArray[leftIndex];
leftIndex++;
k++;
}
// copy rest of the right array
while (rightIndex < rightArray.length) {
numbers[k] = rightArray[rightIndex];
rightIndex++;
k++;
}
}