Merge Sort in Java

Merge sort is an efficient, general-purpose, comparison-based sorting algorithm. It works by dividing an array into two halves, sorting each half, and then merging the sorted halves back together.

Here is an example of how you might implement merge sort in Java:

class MergeSort {

  public static void sort(int[] array) {

    if (array.length > 1) {

      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];

        i++;

      } else {

        array[k] = right[j];

        j++;

      }

      k++;

    }

    while (i < left.length) {

      array[k] = left[i];

      i++;

      k++;

    }

    while (j < right.length) {

      array[k] = right[j];

      j++;

      k++;

    }

  }

}

You can then use the sort method to sort an array as follows:

int[] array = {4, 3, 2, 1};

MergeSort.sort(array);

System.out.println(Arrays.toString(array)); // Outputs [1, 2, 3, 4]