English | 简体中文 | 繁體中文 | Русский язык | Français | Español | Português | Deutsch | 日本語 | 한국어 | Italiano | بالعربية

Java Basic Tutorial

Java Flow Control

Java Array

Java Object-Oriented(I)

Java Object-Oriented(II)

Java Object-Oriented(III)

Java Exception Handling

Java List(List)

Java Queue(Queue)

Java Map collection

Java Set collection

Java input output (I/O)

Java Reader/Writer

Java other topics

Java program implementation of merge sort algorithm

Comprehensive Java Examples

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.

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 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]) {

Comprehensive Java Examples