Merge Sort: Difference between revisions
(18 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
=Internal= | =Internal= | ||
* [[Recursive_Algorithms#Divide_and_Conquer|Divide and Conquer Algorithms]] | |||
* [[Sorting_Algorithms#Sorting_Algorithms|Sorting Algorithms]] | * [[Sorting_Algorithms#Sorting_Algorithms|Sorting Algorithms]] | ||
=Overview= | =Overview= | ||
Merge sort is a [[Algorithms#Divide_and_Conquer|divide-and-conquer]] algorithm. | Merge sort is a [[Algorithms#Divide_and_Conquer|divide-and-conquer]] algorithm. The algorithm was invented by John von Neumann in 1945, and it is still used today as the standard sorting algorithm in a number of programming libraries. | ||
{| class="wikitable" style="text-align: left;" | |||
| [[Algorithm_Complexity#Worst-case_Running_Time|Worst-case time]] || Θ(n log n) | |||
| [[Algorithm_Complexity#Worst-case_Running_Time|Worst-case time]] || Θ(n | |||
|- | |- | ||
| [[Algorithm_Complexity#Average-case_Running_Time|Average-case time]] || Θ(n | | [[Algorithm_Complexity#Average-case_Running_Time|Average-case time]] || Θ(n log n) | ||
|- | |- | ||
| [[Algorithm_Complexity#Best-case_Running_Time|Best-case time]] || | | [[Algorithm_Complexity#Best-case_Running_Time|Best-case time]] || | ||
|} | |} | ||
Because the [[#Combine|combine]] phase of the algorithm makes secondary copies for the entire data array received as argument, merge sort is not considered an in-place sorting algorithm, while [[Quicksort#Overview|QuickSort]] is. | |||
=Algorithm= | =Algorithm= | ||
Merge sort works as follows: | Merge sort works as follows: | ||
# '''Divide''': it divides the initial input array into two roughly equal sub-arrays of n/2 elements each. If n is even, the array is split in two equal halves, if n is odd, the right array is bigger than the left array with one element. | # '''Divide''': it divides the initial input array into two roughly equal sub-arrays of n/2 elements each. If n is even, the array is split in two equal halves, if n is odd, the right array is bigger than the left array with one element. The base case and exit from recurrence happens when we see one-element array. This is the time to stop the recurrence. | ||
# '''Conquer''': it calls itself recursively to sort the sub-arrays produced as result of the previous step. | # '''Conquer''': it calls itself recursively to sort the sub-arrays produced as result of the previous step. | ||
# <span id='Combine'></span>'''Combine''': it merges the two sorted sub-arrays to produce the sorted answer, by invoking an auxiliary Θ(n) procedure. The merge procedure merges the arrays using the same algorithm we would use while combining two sorted piles of cards: we use two sorted input piles, we compare the cards at the top of the input piles, pick the smallest one and place it face down on the table. Removing a card from an input pile uncovers a new card in the respective input pile. We repeat the operation until we deplete one input pile, and then we place the remaining pile face down at the top of the output pile. | # <span id='Combine'></span>'''Combine''': it merges the two sorted sub-arrays to produce the sorted answer, by invoking an auxiliary Θ(n) procedure. The merge procedure merges the arrays using the same algorithm we would use while combining two sorted piles of cards: we use two sorted input piles, we compare the cards at the top of the input piles, pick the smallest one and place it face down on the table. Removing a card from an input pile uncovers a new card in the respective input pile. We repeat the operation until we deplete one input pile, and then we place the remaining pile face down at the top of the output pile. | ||
Line 32: | Line 33: | ||
*/ | */ | ||
public static void mergeSort(int[] a, int from, int to) { | public static void mergeSort(int[] a, int from, int to) { | ||
// | // | ||
// divide | // divide | ||
// | // | ||
int middle = from + (to - from) / 2; | int middle = from + (to - from) / 2; | ||
if (from == middle) { | if (from == middle) { | ||
// | // | ||
// we bottomed out, it means a has at most one element, and it is already sorted, | // we bottomed out, it means a has at most one element, and it is already sorted, | ||
// get out of recurrence. | // get out of recurrence. | ||
// | // | ||
return; | return; | ||
} | } | ||
// | // | ||
// there is a middle that separates non-empty arrays, conquer | // there is a middle that separates non-empty arrays, conquer | ||
// | // | ||
mergeSort(a, from, middle); | mergeSort(a, from, middle); | ||
mergeSort(a, middle, to); | mergeSort(a, middle, to); | ||
// | // | ||
// combine sorted sub-arrays | // combine sorted sub-arrays | ||
// | // | ||
merge(a, from, middle, to); | merge(a, from, middle, to); | ||
} | } | ||
Line 68: | Line 60: | ||
*/ | */ | ||
public static void merge(int[] a, int i, int j, int k) { | public static void merge(int[] a, int i, int j, int k) { | ||
// | // | ||
// make copies | // make copies | ||
// | // | ||
int[] left = new int[j - i]; | int[] left = new int[j - i]; | ||
System.arraycopy(a, i, left, 0, left.length); | System.arraycopy(a, i, left, 0, left.length); | ||
int[] right = new int[k - j]; | int[] right = new int[k - j]; | ||
System.arraycopy(a, j, right, 0, right.length); | System.arraycopy(a, j, right, 0, right.length); | ||
Line 84: | Line 73: | ||
while(l < left.length && r < right.length) { | while(l < left.length && r < right.length) { | ||
if (left[l] <= right[r]) { | if (left[l] <= right[r]) { | ||
a[dest ++] = left[l]; | a[dest ++] = left[l]; | ||
l ++; | l ++; | ||
} | } | ||
else { | else { | ||
a[dest ++] = right[r]; | a[dest ++] = right[r]; | ||
r ++; | r ++; | ||
Line 100: | Line 86: | ||
// drain leftovers | // drain leftovers | ||
// | // | ||
while(l < left.length) { | while(l < left.length) { | ||
a[dest ++] = left[l ++]; | a[dest ++] = left[l ++]; | ||
} | } | ||
while(r < right.length) { | while(r < right.length) { | ||
a[dest ++] = right[r ++]; | a[dest ++] = right[r ++]; | ||
} | } | ||
Line 113: | Line 95: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
= | =Time Complexity Analysis= | ||
One way of estimating the time complexity is to use a recursion tree: {{Internal|Recursion_Trees#Recursion_Tree_Example_for_Merge_Sort|Recursion Tree Example for Merge Sort}} | |||
= | Another way is to use the [[Master_Method#Examples|master theorem]]. The running time of merge sort can be expressed by the following [[Recursive_Algorithms_Complexity#Recurrences|recurrence]]: | ||
<font size=-1> | |||
│ c if n == 1 | |||
T(n) = │ | |||
│ 2T(n/2) + cn if n > 1 | |||
</font> | |||
In the context of the [[Master_Method#Examples|master theorem]], the number of subproblems (a) is 2, the subproblem size is n/2, so b is 2, and the combine phase of the algorithm performs Θ(n<sup>1</sup>) work, so d is 1. a/b<sup>d</sup> is 1, so according complexity is Θ(n log n). | |||
More details in [[CLRS]] page 35. | |||
=Correctness= | |||
<font color=darkgray> | <font color=darkgray>Analyze [[Loop_Invariant|loop invariants]]. [[CLRS]] page 31.</font> |
Latest revision as of 19:11, 9 November 2021
Internal
Overview
Merge sort is a divide-and-conquer algorithm. The algorithm was invented by John von Neumann in 1945, and it is still used today as the standard sorting algorithm in a number of programming libraries.
Worst-case time | Θ(n log n) |
Average-case time | Θ(n log n) |
Best-case time |
Because the combine phase of the algorithm makes secondary copies for the entire data array received as argument, merge sort is not considered an in-place sorting algorithm, while QuickSort is.
Algorithm
Merge sort works as follows:
- Divide: it divides the initial input array into two roughly equal sub-arrays of n/2 elements each. If n is even, the array is split in two equal halves, if n is odd, the right array is bigger than the left array with one element. The base case and exit from recurrence happens when we see one-element array. This is the time to stop the recurrence.
- Conquer: it calls itself recursively to sort the sub-arrays produced as result of the previous step.
- Combine: it merges the two sorted sub-arrays to produce the sorted answer, by invoking an auxiliary Θ(n) procedure. The merge procedure merges the arrays using the same algorithm we would use while combining two sorted piles of cards: we use two sorted input piles, we compare the cards at the top of the input piles, pick the smallest one and place it face down on the table. Removing a card from an input pile uncovers a new card in the respective input pile. We repeat the operation until we deplete one input pile, and then we place the remaining pile face down at the top of the output pile.
/**
* Merge sorts in-place in a[] but it makes secondary copies.
*
* @param to indicates the first array element outside the area to sort.
* It may be equal with the array length, if we want to sort the entire
* array.
*/
public static void mergeSort(int[] a, int from, int to) {
//
// divide
//
int middle = from + (to - from) / 2;
if (from == middle) {
//
// we bottomed out, it means a has at most one element, and it is already sorted,
// get out of recurrence.
//
return;
}
//
// there is a middle that separates non-empty arrays, conquer
//
mergeSort(a, from, middle);
mergeSort(a, middle, to);
//
// combine sorted sub-arrays
//
merge(a, from, middle, to);
}
/**
* Combines in place. Assumes that the sub-arrays [i, j) and [j, k)
* are sorted and merges them in-place.
*/
public static void merge(int[] a, int i, int j, int k) {
//
// make copies
//
int[] left = new int[j - i];
System.arraycopy(a, i, left, 0, left.length);
int[] right = new int[k - j];
System.arraycopy(a, j, right, 0, right.length);
int l = 0;
int r = 0;
int dest = i;
while(l < left.length && r < right.length) {
if (left[l] <= right[r]) {
a[dest ++] = left[l];
l ++;
}
else {
a[dest ++] = right[r];
r ++;
}
}
//
// drain leftovers
//
while(l < left.length) {
a[dest ++] = left[l ++];
}
while(r < right.length) {
a[dest ++] = right[r ++];
}
}
Time Complexity Analysis
One way of estimating the time complexity is to use a recursion tree:
Another way is to use the master theorem. The running time of merge sort can be expressed by the following recurrence:
│ c if n == 1 T(n) = │ │ 2T(n/2) + cn if n > 1
In the context of the master theorem, the number of subproblems (a) is 2, the subproblem size is n/2, so b is 2, and the combine phase of the algorithm performs Θ(n1) work, so d is 1. a/bd is 1, so according complexity is Θ(n log n).
More details in CLRS page 35.
Correctness
Analyze loop invariants. CLRS page 31.