What is Merge Sort?

Merge Sort is a sorting technique that involves breaking down one collection into two parts to either sort the component elements in ascending or descending order.

Merge Sort Algorithm

It uses the recursive function call to break down itself until a single unit in each list is left with. Recursive functions are ones that call itself. An unsorted list is first broken down into 2 equal halves (if possible). Those two halves are then then broken down into further halves until one element is left with in each leaf node. Thereafter, the same path is followed to join the leaves but while they are simultaneously being sorted alongside.

This block diagram will help understand the flow:

Example with Code

class MergeSort {

void merge (int arr[], int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;

int L[] = new int[n1];
int R[] = new int[n2];

for (int i = 0; i < n1; ++i)
L[i] = arr[l + i];
for (int j = 0; j < n2; ++j)
R[j] = arr[m + 1 + j];

/* Merge the temp arrays */
int i = 0, j = 0;
int k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++; }
else {
arr[k] = R[j];
j++;
}
k++; }
while (i < n1) {
arr[k] = L[i];
i++;
k++; }
while (j < n2) {
arr[k] = R[j];
j++;
k++; } }

// merge()
void sort(int arr[], int l, int r) {
if (l < r) {
// middle point
int m = (l + r) / 2;
sort(arr, l, m);
sort(arr, m + 1, r);
merge(arr, l, m, r);
}
}

static void printArray(int arr[]) {
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}

public static void main(String args[]) {
int arr[] = { 5, 7, 1, 89, 34, 6 };
System.out.println("Given Array");
printArray(arr);
MergeSort ob = new MergeSort();
ob.sort(arr, 0, arr.length - 1);
System.out.println("\nSorted array");
printArray(arr);
}
}

OUTPUT

1
5
6
7
34
89