While the list has more than one elements:
Divide the list in two halves
Sort first half
Sort second half
Merge sorted lists
This strategy is called divide-and-conquer method. We take advantage of the recursion technique in merge sort. So there are two operations happening recursively, dividing the list into two halves and merging them back. The base case for the recursion is when the list size is one.
Following diagram illustrates merge sort algorithm:
The number of times the list of size n is divided is equal to log(n). Where log(n) resembles to height of a virtual tree created during recursive calls to merge sort.
The time complexity of merge function is linear i.e. it takes exactly n operations to merge two lists of size n/2. Hence the overall time complexity of merge sort is O(n log n).
Here is a java implementation of a merge sort algorithm:
public class MergeSort {
public static void sort(int[] a) {
int left = 0; // start index of the list
int right = a.length - 1; // end index of the list
int[] aux = new int[a.length];
mergeSort(a, aux, left, right);
}
private static void mergeSort(int[] a, int[] aux,
int left, int right) {
if (left < right) {
int center = (left + right) / 2;
mergeSort(a, aux, left, center);
mergeSort(a, aux, center + 1, right);
merge(a, aux, left, center + 1, right);
}
}
private static void merge(int[] a, int[] aux, int left,
int right, int rightEnd) {
int leftEnd = right - 1;
int numOfElements = rightEnd - left + 1;
int k = left; // start index to save merged result
while (left <= leftEnd && right <= rightEnd) {
if (a[left] <= a[right]) {
aux[k++] = a[left++];
} else {
aux[k++] = a[right++];
}
}
// copy leftover elements from first list
while (left <= leftEnd) {
aux[k++] = a[left++];
}
// copy leftover elements from second list
while (right <= rightEnd) {
aux[k++] = a[right++];
}
// copy auxiliary back to a
for (int i = 0; i < numOfElements; i++, rightEnd--) {
a[rightEnd] = aux[rightEnd];
}
}
}
Test program to test merge sort algorithm:
import java.util.Random;
public class SortTest {
public final static int LENGTH = 10;
public static void main(String[] args) {
int[] a = new int[LENGTH];
Random random = new Random();
for (int i = 0; i < LENGTH; i++) {
a[i] = random.nextInt(100);
}
System.out.println("Before sort : ");
display(a);
long startTime = System.nanoTime();
MergeSort.sort(a);
long endTime = System.nanoTime();
System.out.println("After sort : ");
display(a);
double sortTime = (endTime - startTime) / 1000000.0;
System.out.println("Estimate Time for Sort: "
+ sortTime + " milliseconds.");
}
private static void display(int[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]);
System.out.print(" ");
}
System.out.println();
}
}
