Merge Sort (Java)

The universally used sorting algorithm ..

Merge sort is a sorting algorithm that uses O(n log n) (Big O Notation) comparisons to sort a list of n elements. 


Merge sort uses the divide and conquer strategy, dividing the list of elements into two sub-lists, sorts them and merges them back together to a sorted list. 


The strength of merge sort is that you always merge two lists that you know are already sorted, therefore the merging on each level will only take O(n) operations.


No easy way to understand it .. hope this helps ;))

If you really want to tax your brain with mathematics :P, then http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/mergeSort.htm is the place for you !


This link also has a very good explanation for Merge Sort : http://www.mycstutorials.com/articles/sorting/mergesort

Java Code

public class Mergesort {
 private int[] numbers;
 private int[] helper;

 private int number;

 public void sort(int[] values) {
  this.numbers = values;
  number = values.length;
  this.helper = new int[number];
  mergesort(0, number - 1);
 }

 private void mergesort(int low, int high) {
  // Check if low is smaller then high, if not then the array is sorted
  if (low < high) {
   // Get the index of the element which is in the middle
   int middle = (low + high) / 2;
   // Sort the left side of the array
   mergesort(low, middle);
   // Sort the right side of the array
   mergesort(middle + 1, high);
   // Combine them both
   merge(low, middle, high);
  }
 }

 private void merge(int low, int middle, int high) {

  // Copy both parts into the helper array
  for (int i = low; i <= high; i++) {
   helper[i] = numbers[i];
  }

  int i = low;
  int j = middle + 1;
  int k = low;
  // Copy the smallest values from either the left or the right side back
  // to the original array
  while (i <= middle && j <= high) {
   if (helper[i] <= helper[j]) {
    numbers[k] = helper[i];
    i++;
   } else {
    numbers[k] = helper[j];
    j++;
   }
   k++;
  }
  // Copy the rest of the left side of the array into the target array
  while (i <= middle) {
   numbers[k] = helper[i];
   k++;
   i++;
  }

 }
}