Algorithms / Arrays / Merge Sort

algorithms-arrays-mergeSort.java

package org.joeltong.test;

import java.util.Arrays;

public class MergeSort {

  static void mergeSort(int[] arr) {
    mergeSort(arr, 0, arr.length - 1);
  }


  static void mergeSort(int[] arr, int l, int r) {
    if (r <= l) {
      return;
    }

    int m = (l + r) / 2;
    mergeSort(arr, l, m);
    mergeSort(arr, m + 1, r);
    merge(arr, l, m, r);
  }


  static void merge(int[] arr, int l, int m, int r) {
    int[] arrI = new int[m - l + 1];
    int[] arrJ = new int[r - m];

    // copy arrays
    for (int a = 0; a < arrI.length; a++) {
      arrI[a] = arr[l + a];
    }

    for (int a = 0; a < arrJ.length; a++) {
      arrJ[a] = arr[m + 1 + a];
    }

    int i = 0;
    int j = 0;
    int k = l;

    while (i < arrI.length && j < arrJ.length) {
      if (arrI[i] < arrJ[j]) {
        arr[k] = arrI[i];
        i++;
      } else {
        arr[k] = arrJ[j];
        j++;
      }
      k++;
    }

    // copy remainder
    while(i < arrI.length) {
      arr[k] = arrI[i];
      i++;
      k++;
    }

    while(j < arrJ.length) {
      arr[k] = arrJ[j];
      j++;
      k++;
    }
  }


  public static void main(String[] args) {
    int[] arr = {34,2,34,34,7,5,4,2,6,8,5,443,22,5,7,8,75,10};
    mergeSort(arr);
    System.out.println(Arrays.toString(arr));
  }
}