Merge Sort with Java code

Image source: https://webdocs.cs.ualberta.ca

Merge sort is an efficient comparison-based sorting algorithm. It works by dividing an array into two halves, recursively sorting each half, and then merging the two sorted halves back together. The merge operation is the key step that ensures that the final, merged array is sorted.

Here’s a Java implementation of the merge sort algorithm:

import java.util.Arrays;

public class MergeSort {

 public static void sort(int[] array) {
  if (array.length <= 1) {
   return;
  }
  int mid = array.length / 2;
  int[] left = Arrays.copyOfRange(array, 0, mid);
  int[] right = Arrays.copyOfRange(array, mid, array.length);
  sort(left);
  sort(right);
  merge(array, left, right);
 }

 private static void merge(int[] array, int[] left, int[] right) {
  int i = 0, j = 0, k = 0;
  while (i < left.length && j < right.length) {
   if (left[i] < right[j]) {
    array[k++] = left[i++];
   } else {
    array[k++] = right[j++];
   }
  }
  while (i < left.length) {
   array[k++] = left[i++];
  }
  while (j < right.length) {
   array[k++] = right[j++];
  }
 }

 public static void main(String args[]) {
  int[] array = new int[] { 4, 109, 7, 39, 24, 52, 1 };
  sort(array);
  Arrays.stream(array).forEach(System.out::println);
 }
}

The sort method is the entry point to the algorithm. It takes an array of integers as its parameter and sorts it in place. The method first checks…