Merge Sort is a divide-and-conquer algorithm. It is the most commonly used best sorting algorithm and frequently asked in interview question.
Basic:
Suppose the sequence we need to sort is A[] whose length is n. We will be using the following terms during the explanation of merge sort :A[] - Sequence we need to sort.
p - Index of the first element of the sequence.
q - Index of the middle element of the sequence.
r - Index of the last element of the sequence.
n - Length of the sequence.
Example:
Here,
p = 1
q = 3
r = 5
n = 5.
Steps:
1) Divide Step:
i) If the sequence has less than 2 elements, return the sequence (no sorting required, sequence is alreadysorted).
// For sequence with 0 or 1 elements, p == r
for n = 0, p = 0, r = 0
for n = 1, p = 1, r = 1
// For sequence with more than 1 elements, p < r
for n = 2, p = 1, r = 2
.
.
i.e. for divide step, value of p has to be less than r.
ii) Otherwise split the sequence from middle into two sub sequences,
 |
| Basic Divide Step |
q = ( p + r ) / 2 // get middle index.
Two Sub sequences s1 = A[p ....q] and s2 = A [ (q + 1) ... r].
Pseudo code for Divide:
if ( p < r ) // sequence has more than 1 elements.
q = ( p + r ) / 2; // divide step. (No need to show the split sequence step)
2) Conquer Step:
During this step we sort the two sub sequences s1 and s2 using Merge-Sort. This step is performed by recursively calling Merge-sort function on each of the sub sequences. There is no clear demarcation between the divide-conquer or conquer-combine step. The conquer calls Merge-Sort function on each sub sequence and each Merge-Sort function itself performs all 3 steps (Divide, Conquer, Combine).
 |
| Recursively perform Divide Step |
Pseudo code for Conquer:
if ( p < r )
q = ( p + r ) / 2;
Merge-Sort(A, p, q); // Conquer step for sequence s1.
Merge-Sort(A, q+1, r). // Conquer step for sequence s2.
3) Combine Step:
During this step we merge the two sorted sub sequences to obtain the final sorted sequence. This step is performed by calling Merge function on two sorted sub sequences s1 and s2.
Pseudo code for Merge:
Merge(A, p, q , r); // We can distinguish between sub sequence s1 and s2 with help of middle index q.
 |
| Recursively perform Combine Step |
Algorithm For Merge Sort
Merge-Sort (A, p , r)
if p < r // Base check case.
q = (p + q) / 2 // Divide Step.
Merge-Sort ( A, p, q); // Conquer Step.
Merge-Sort ( A, q+1, r); // Conquer Step.
Merge (A, p, q, r); // Combine Step.
Merge(A, p, q, r)
n1 ← q − p + 1
n2 ← r − q Create sub sequence L[1 . . n1 + 1] and R[1 . . n2 + 1]
for i ← 1 TO n1 DO L[i] ← A[p + i − 1]
for j ← 1 TO n2 R[j] ← A[q + j ]
L[n1 + 1] ← ∞
R[n2 + 1] ← ∞
i ← 1
j ← 1
for k ← p TO r if L[i ] ≤ R[ j]
A[k] ← L[i]
i ← i + 1
else A[k] ← R[j]
j ← j + 1
n1 ← q − p + 1
n2 ← r − q Create sub sequence L[1 . . n1 + 1] and R[1 . . n2 + 1]
for i ← 1 TO n1 DO L[i] ← A[p + i − 1]
for j ← 1 TO n2 R[j] ← A[q + j ]
L[n1 + 1] ← ∞
R[n2 + 1] ← ∞
i ← 1
j ← 1
for k ← p TO r if L[i ] ≤ R[ j]
A[k] ← L[i]
i ← i + 1
else A[k] ← R[j]
j ← j + 1
Analysis:
Merge sort run time calculation :
1) Divide Phase:
Each divide step requires O(1) run-time. The divide phase takes log(n) steps to completely divide the
sequence into individual segments.
No of steps involved in divide phase = Log(n).
Time required to perform each divide step = O(1).
Total time required for divide phase = No of steps involved in divide phase * Time required to perform
each divide step
= Log(n) * 1
= Log(n).
2) Combine Phase:
1) Divide Phase:
Each divide step requires O(1) run-time. The divide phase takes log(n) steps to completely divide the
sequence into individual segments.
No of steps involved in divide phase = Log(n).
Time required to perform each divide step = O(1).
Total time required for divide phase = No of steps involved in divide phase * Time required to perform
each divide step
= Log(n) * 1
= Log(n).
2) Combine Phase:
During each combine step, while iterating through the two sub sequences, comparison step (read
operation )requires O(1) time, but write step requires n steps. Also we need to perform combine log(n)
times as they are recursively called same as divide phase.
No of steps involved in combine phase = Log(n).
Time required to perform each combine step = n.
Total time required for divide phase = No of steps involved in divide phase * Time required to perform
each divide step
= Log(n) * n
= n Log(n).
Total Run-Time of Merge-Sort:
Total Run-time of Merge-Sort = Total time required for Divide Phase + Total time required for Combine
Phase
= Log(n) + n Log(n)
= n Log(n).
(Note: we consider the case where we recursively divide the sequence into two parts, so the base of the log function is 2).
Best case : O(n logn)
Average case : O(n logn)
Worst case : O(n logn)
Run-time of merge sort is same for best, average and worst case. This is because regardless of the sequence is sorted or unsorted, it is going to perform all the steps for division and combination. So the run-time of merge-sort is same for all cases.
Phase
= Log(n) + n Log(n)
= n Log(n).
(Note: we consider the case where we recursively divide the sequence into two parts, so the base of the log function is 2).
Best case : O(n logn)
Average case : O(n logn)
Worst case : O(n logn)
Run-time of merge sort is same for best, average and worst case. This is because regardless of the sequence is sorted or unsorted, it is going to perform all the steps for division and combination. So the run-time of merge-sort is same for all cases.
Merge sort Java Implementation :
public class InPlaceMergeSort {
private int[] arr;
void setValue(int[] values) {
arr = values;
}
void merge(int start, int mid, int end) {
int j = mid + 1;
for (int i = 0; i <= mid && j <= end; i++) {
if (arr[i] > arr[j]) {
swapElements(arr, i, j);
}
for (int k = j + 1; k < end; k++) {
if (arr[j] > arr[k]) {
swapElements(arr, j, k);
}
}
}
}
int[] mergeSort(int start, int end) {
if (start < end) {
int mid = (start + end) / 2;
mergeSort(start, mid);
mergeSort(mid + 1, end);
merge(start, mid, end);
}
return arr;
}
void swapElements(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String args[]) {
int[] arr = { 1, 4, 2, 3, 2, 5, 3, 7, 8 };
InPlaceMergeSort obj = new InPlaceMergeSort();
obj.setValue(arr);
arr = obj.mergeSort(0, arr.length - 1);
System.out.print("Output : ");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
private int[] arr;
void setValue(int[] values) {
arr = values;
}
void merge(int start, int mid, int end) {
int j = mid + 1;
for (int i = 0; i <= mid && j <= end; i++) {
if (arr[i] > arr[j]) {
swapElements(arr, i, j);
}
for (int k = j + 1; k < end; k++) {
if (arr[j] > arr[k]) {
swapElements(arr, j, k);
}
}
}
}
int[] mergeSort(int start, int end) {
if (start < end) {
int mid = (start + end) / 2;
mergeSort(start, mid);
mergeSort(mid + 1, end);
merge(start, mid, end);
}
return arr;
}
void swapElements(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String args[]) {
int[] arr = { 1, 4, 2, 3, 2, 5, 3, 7, 8 };
InPlaceMergeSort obj = new InPlaceMergeSort();
obj.setValue(arr);
arr = obj.mergeSort(0, arr.length - 1);
System.out.print("Output : ");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
No comments:
Post a Comment