by BehindJava

# Data Structures - Merge Sort Algorithm

Home » datastructures » Data Structures - Merge Sort Algorithm

In this tutorial, we are going to learn about merge sort in detail and its algorithmic implementation.

# Merge Sort

• Divide and Conquer algorithm.
• Recursive in structure.
• Divide the problem into sub-problems that are similar to the original but smaller in size.
• Conquer the sub-problems by solving them recursively. If they are small enough, just solve them in a straight forward manner.
• Combine the solutions to create a solution to the original problem.

# Merge Sort Algorithm

Merge-Sort (A, p, r)
INPUT: a sequence of n numbers stored in array A.
OUTPUT: an ordered sequence of n numbers.
MergeSort (A, p, r) // sort A[p..r] by divide & conquer.

1. if p < r
2. then q<-[(p+r)/2]
3. MergeSort (A, p, q)
4. MergeSort (A, q+1, r)
5. Merge (A, p, q, r) // merges A[p..q] with A[q+1..r].

# Merge Sort Example

• Sorting Problem: Sort a sequence of n elements into non-decreasing order.
• Divide: Divide the n-element sequence to be sorted 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.

# Insertion Sort Programmatic Implementation in Java

``````public class MergeSort {

public static void main(String[] args) {
int[] intArray = { 20, 35, -15, 7, 55, 1, -22 };
mergeSort(intArray, 0, intArray.length);
for (int i = 0; i < intArray.length; i++) {
System.out.print(intArray[i]+ " ");
}}
// { 20, 35, -15, 7, 55, 1, -22 }
public static void mergeSort(int[] input, int start, int end) {
if (end - start < 2) {
return;
}
int mid = (start + end) / 2;
mergeSort(input, start, mid);
mergeSort(input, mid, end);
merge(input, start, mid, end);
}
// { 20, 35, -15, 7, 55, 1, -22 }
public static void merge(int[] input, int start, int mid, int end) {
if (input[mid - 1] <= input[mid]) {
return;
}
int i = start;
int j = mid;
int tempIndex = 0;
int[] temp = new int[end - start];
while (i < mid && j < end) {
temp[tempIndex++] = input[i] <= input[j] ? input[i++] : input[j++];
}
System.arraycopy(input, i, input, start + tempIndex, mid - i);
System.arraycopy(temp, 0, input, start, tempIndex);
}}``````

Output:

``-22 -15 1 7 20 35 55 ``

# Analysis of Merge Sort

• Running time T(n) of Merge Sort:

• Divide: computing the middle takes O(1)
• Conquer: solving 2 sub problems takes 2T(n/2)
• Combine: merging n elements takes O(n)
• Total: T(n) = O(1) if n = 1.
T(n) = 2T(n/2) + O(n) if n > 1.
=> T(n) = O(n log n).