Merge sort is a stable sorting algorithm based on divide and conquer principle with asymptotic complexity . The fundamental idea behind merge sort is merging of already sorted subarrays using additional helper array of size
.
Merge sort was devised in 1945 by John von Neumann.
Description
Merging
Let's suppose that we have two lists (A, B) sorted in descending order. We can merge them into one sorted list (C) using following procedure.
In every step the procedure compares the lists head elements and picks the higher one. Than it copies the element into the list C and removes it from the original list. The algorithm repeats this step until one of the lists A or B is empty. When this happens, procedure copies rest of the remaining list to the C (a deletes the elements in original array).
In fact merge sort always merges two subarrays, which are adjacent to each other. Hence the procedure uses two pointers pointing to the heads of each lists. Than it selects the higher value from one list, copies it to the appropriate position in helper array and than it moves the respective pointer to the next position (new head of the list).
When all the elements are sorted in the helper array, procedure copies them into the original array and overwrites the unsorted lists.
Splitting
So far, we have omitted the fact, how the algorithm gets the already sorted adjacent subarrays. The splitting part of merge sort has the whole array as its input. Merge sort splits this array into two parts of the same size, than it splits recursively into four parts and so one. When it reaches subarrays containing only one element, the recursion stops. At this point algorithm has two adjacent arrays, each containing only one element (which are trivially sorted).
The sorting itself
Merge sort now returns from recursion calling merge procedure on both halves of the array – which must be sorted, because they are either trivial or already merged. When merge sort terminates (returns completely from the recursion), the whole array is sorted in descending order.
Code
/**
* Merge sort (descending order)
* @param array array to be sorted
* @param aux auxiliary array of the same size as array
* @param left first index, which can be touched
* @param right last index, which can be touched
*/
public static void mergeSort(int[] array, int[] aux, int left, int right) {
if (left == right) return;
int middleIndex = (left + right)/2;
mergeSort(array, aux, left, middleIndex);
mergeSort(array, aux, middleIndex + 1, right);
merge(array, aux, left, right);
for (int i = left; i <= right; i++) {
array[i] = aux[i];
}
}
/**
* Merge procedure for merge sort
* @param array array to be merged
* @param aux auxiliary array of the same size as array
* @param left first index, which can be touched
* @param right last index, which can be touched
*/
private static void merge(int[] array, int[] aux, int left, int right) {
int middleIndex = (left + right)/2;
int leftIndex = left;
int rightIndex = middleIndex + 1;
int auxIndex = left;
while (leftIndex <= middleIndex && rightIndex <= right) {
if (array[leftIndex] >= array[rightIndex]) {
aux[auxIndex] = array[leftIndex++];
} else {
aux[auxIndex] = array[rightIndex++];
}
auxIndex++;
}
while (leftIndex <= middleIndex) {
aux[auxIndex] = array[leftIndex++];
auxIndex++;
}
while (rightIndex <= right) {
aux[auxIndex] = array[rightIndex++];
auxIndex++;
}
}
/**
* Merge sort (descending order)
* @param array array to be sorted
* @param aux auxiliary array of the same size as array
* @param left first index, which can be touched
* @param right last index, which can be touched
*/
void mergeSort(int array[], int aux[], int left, int right) {
if (left == right) return;
int middleIndex = (left + right)/2;
mergeSort(array, aux, left, middleIndex);
mergeSort(array, aux, middleIndex + 1, right);
merge(array, aux, left, right);
for (int i = left; i <= right; i++) {
array[i] = aux[i];
}
}
/**
* Merge procedure for merge sort
* @param array array to be merged
* @param aux auxiliary array of the same size as array
* @param left first index, which can be touched
* @param right last index, which can be touched
*/
void merge(int array[], int aux[], int left, int right) {
int middleIndex = (left + right)/2;
int leftIndex = left;
int rightIndex = middleIndex + 1;
int auxIndex = left;
while (leftIndex <= middleIndex && rightIndex <= right) {
if (array[leftIndex] >= array[rightIndex]) {
aux[auxIndex] = array[leftIndex++];
} else {
aux[auxIndex] = array[rightIndex++];
}
auxIndex++;
}
while (leftIndex <= middleIndex) {
aux[auxIndex] = array[leftIndex++];
auxIndex++;
}
while (rightIndex <= right) {
aux[auxIndex] = array[rightIndex++];
auxIndex++;
}
}
/**
* Merge sort (descending order)
* @param array array to be sorted
* @param aux auxiliary array of the same size as array
* @param left first index, which can be touched
* @param right last index, which can be touched
*/
public static void MergeSort(int[] array, int[] aux, int left, int right)
{
if (left == right) return;
int middleIndex = (left + right) / 2;
MergeSort(array, aux, left, middleIndex);
MergeSort(array, aux, middleIndex + 1, right);
Merge(array, aux, left, right);
for (int i = left; i <= right; i++)
{
array[i] = aux[i];
}
}
/**
* Merge procedure for merge sort
* @param array array to be merged
* @param aux auxiliary array of the same size as array
* @param left first index, which can be touched
* @param right last index, which can be touched
*/
private static void Merge(int[] array, int[] aux, int left, int right)
{
int middleIndex = (left + right) / 2;
int leftIndex = left;
int rightIndex = middleIndex + 1;
int auxIndex = left;
while (leftIndex <= middleIndex && rightIndex <= right)
{
if (array[leftIndex] >= array[rightIndex])
{
aux[auxIndex] = array[leftIndex++];
}
else
{
aux[auxIndex] = array[rightIndex++];
}
auxIndex++;
}
while (leftIndex <= middleIndex)
{
aux[auxIndex] = array[leftIndex++];
auxIndex++;
}
while (rightIndex <= right)
{
aux[auxIndex] = array[rightIndex++];
auxIndex++;
}
}