 Java Program to Implement Merge Sort Algorithm

# Java Program to Implement Merge Sort Algorithm

#### In this example, we will learn to execute merge sort algorithm in Java.

To understand this example, you should have the knowledge of the following Java programming topics:

## Example: Java Program to Implement Merge Sort Algorithm

``````import java.util.Arrays;

// Merge sort in Java

class Main {

// Merge two sub arrays L and M into array
void merge(int array[], int p, int q, int r) {

int n1 = q - p + 1;
int n2 = r - q;

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

// fill the left and right array
for (int i = 0; i < n1; i++)
L[i] = array[p + i];
for (int j = 0; j < n2; j++)
M[j] = array[q + 1 + j];

// Maintain current index of sub-arrays and main array
int i, j, k;
i = 0;
j = 0;
k = p;

// Until we reach either end of either L or M, pick larger among
// elements L and M and place them in the correct position at A[p..r]
// for sorting in descending
// use if(L[i] >= <[j])
while (i < n1 && j < n2) {
if (L[i] <= M[j]) {
array[k] = L[i];
i++;
} else {
array[k] = M[j];
j++;
}
k++;
}

// When we run out of elements in either L or M,
// pick up the remaining elements and put in A[p..r]
while (i < n1) {
array[k] = L[i];
i++;
k++;
}

while (j < n2) {
array[k] = M[j];
j++;
k++;
}
}

// Divide the array into two sub arrays, sort them and merge them
void mergeSort(int array[], int left, int right) {
if (left < right) {

// m is the point where the array is divided into two sub arrays
int mid = (left + right) / 2;

// recursive call to each sub arrays
mergeSort(array, left, mid);
mergeSort(array, mid + 1, right);

// Merge the sorted sub arrays
merge(array, left, mid, right);
}
}

public static void main(String args[]) {

// created an unsorted array
int[] array = { 6, 5, 12, 10, 9, 1 };

Main ob = new Main();

// call the method mergeSort()
// pass argument: array, first index and last index
ob.mergeSort(array, 0, array.length - 1);

System.out.println("Sorted Array:");
System.out.println(Arrays.toString(array));
}
}
``````

Output 1

```Unsorted Array:
[6, 5, 12, 10, 9, 1]
Sorted Array:
[1, 5, 6, 9, 10, 12]```

Here, the elements of the array are sorted in ascending order. If we want to sort the elements in descending order, then inside the first `while` loop of the `merge()` method, we can change the code as:

``````// the less than sign is changed to greater than
if (L[i] >= M[j]) {``````