English | 简体中文 | 繁體中文 | Русский язык | Français | Español | Português | Deutsch | 日本語 | 한국어 | Italiano | بالعربية
In this example, we will learn to perform the merge sort algorithm in Java.
Before learning the merge sort algorithm in Java, make sure you understand the working principle of the merge sort algorithm.
import java.util.Arrays; //Merge sort in Java class Main { //Merge two sub-arrays L and M into the 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 arrays 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 the current index of the sub-array and the main array int i, j, k; i = 0; j = 0; k = p; //Until we reach either end of L or M, then choose the larger one //Elements L and M, and place them in the correct position in A[p..r]. //Descending order sorting //Using 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 the elements in L or M are exhausted // Merge the remaining elements into 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 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 for each sub-array mergeSort(array, left, mid); mergeSort(array, mid + 1, right); //Merge the sorted subarrays merge(array, left, mid, right); } } public static void main(String args[]) { //Create an unsorted array int[] array = { 6, 5, 12, 10, 9, 1 }; Main ob = new Main(); //Call the mergeSort() method //Pass parameters: array, first index, and last index ob.mergeSort(array, 0, array.length - 1); System.out.println("Sorted array:"); System.out.println(Arrays.toString(array)); } }
Output1
Unsorted array: [6, 5, 12, 10, 9, 1] Sorted array: [1, 5, 6, 9, 10, 12]
In this case, the elements of the array are sorted in ascending order. If you want to sort the elements in descending order, you can change the code inside the first while loop of the merge() method as follows:
Change the less than sign to greater if (L[i] >= M[j]) {