In this source code example, we will write a Java program to demonstrate how to implement the Merge Sort algorithm in Java.

Merge sort is a divide-and-conquer sorting algorithm that works by recursively dividing the input list into smaller sublists until each sublist consists of a single element, and then merging the sublists back together in sorted order.

Merge Sort Source Code in Java

public class MergeSort {

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

   public void sort(int[] arr, int[] temp, int low, int high) {
      if (low < high) { // base case
         int mid = low + (high - low) / 2; // overflow condition (low + high) / 2;
         sort(arr, temp, low, mid);
         sort(arr, temp, mid + 1, high);
         merge(arr, temp, low, mid, high);
      }
   }

   private void merge(int[] arr, int[] temp, int low, int mid, int high) {
      for (int i = low; i <= high; i++) {
         temp[i] = arr[i];
      }
      int i = low; // traverse left sorted subarray
      int j = mid + 1; // traverse right sorted subarray
      int k = low; // will merge both arrays into original array (arr)

      while (i <= mid && j <= high) {
         if (temp[i] <= temp[j]) {
            arr[k] = temp[i];
            i++;
         } else {
            arr[k] = temp[j];
            j++;
         }
         k++;
      }

      while (i <= mid) {
         arr[k] = temp[i];
         k++;
         i++;
      }
   }

   public static void main(String[] args) {
      int[] arr = new int[] { 9, 5, 2, 4, 3, -1 };
      MergeSort ms = new MergeSort();
      ms.sort(arr, new int[arr.length], 0, arr.length - 1);
      ms.printArray(arr);
   }

}

Output:

-1 2 3 4 5 9 

Merge sort has a time complexity of O(n log n), making it more efficient than other sorting algorithms for large lists. It is also a stable sort, meaning that the order of elements with equal keys is preserved. However, merge sort requires additional space to store the sublists during the recursive steps, so it is not an in-place sort.