MergeSort.java

MergeSort.java

public class MergeSort {

  public static void main(String[] args) {
    int[] numbers = {4, 6, 2, 25234, 34, 5};
    MergeSort m = new MergeSort(numbers);
    m.sort();
    for (int i = 0; i < numbers.length; i++) {
      System.out.print(numbers[i] + " ");
    }
  }

  private int[] numbers;
  private int[] helper;

  public MergeSort(int[] numbers) {
    this.helper = new int[numbers.length];
    this.numbers = numbers;
  }

  public void sort() {
    mergeSort(0, numbers.length-1);
  }

  public void mergeSort(int start, int end) {
    if (start < end) {
      int mid = (start + end) / 2;
      mergeSort(0, mid);
      mergeSort(mid+1, end);
      merge(start, mid, end);
    }
  }

  // At this point, the lists start..mid and mid+1..high are both sorted.
  private void merge(int low, int mid, int high) {
    // setup helper
    for (int i = low; i <= high; i++) {
      helper[i] = numbers[i];
    }

    int i = low; // iterate on first array
    int j = mid+1; // iterate on second array
    int k = low; // iterate on numbers

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

    // Copy rest of left side. Right side is already sorted.
    while (i <= mid) {
      numbers[k] = helper[i];
      k++;
      i++;
    }
  }

}