Sorting algorithms 4 - Merge sort

Merge sort is faster and efficient than bubble,insertion and selection sorts. But it is not efficient than quick and shell sorts. Time wise merge sort is efficient but this comes with a penalty. That is we need more additional space for merge sort. The basic of merge sort is partition the array in to smaller pieces using recursion and merge them so that you will have a sorted array.

Process

• Choose a pivot element to partition. Typically middle element of the array is better.
• Create 2 sub arrays left and right. Size of left and right should be 0 to middle and middle to original array element size.
• Fill left and right sub arrays from the original array.
• Recursively do these steps until you have sub arrays of singe element. Which means the base case for recursion is sub array elements should not be less than 1.  
• When you have single elements you can start merging them to get a sorted array.Partitioning until single elements happens because single elements are already sorted.
• Now we can compare elements from left array and right array.
• Until left array elements or right array elements are over, compare them and insert the least element to the array. 
• When one array is over you can add remaining arrays elements to the sorted array in a sorted order.
• Tada ! you have a sorted array.

 public void mergeSort(int[] a) {
  int n = a.length;

  // Base case for partitioning
  // Array with single element is already sorted
  if (n == 1)
   return;

  int middle = n / 2;
  // Create sub arrays
  int[] left = new int[middle];
  int[] right = new int[n - middle];

  // Fill sub arrays
  for (int i = 0; i < middle; i++) {
   left[i] = a[i];
  }
  for (int i = middle; i < n; i++) {
   right[i - middle] = a[i];
  }

  // recursively partition until 1 element is there
  mergeSort(left);
  mergeSort(right);

  // Merge sub arrays
  Merge(left, right, a);

 }

 public void Merge(int[] left, int[] right, int[] a) {

  int leftArrItems = left.length;
  int rightArrItems = right.length;

  // i for left array looping
  // j for right array looping
  // k for a array looping
  int i = 0;
  int j = 0;
  int k = 0;

  while (i < leftArrItems && j < rightArrItems) {

   // Decides from what sub array to pick to fill final array
   if (left[i] < right[j]) {
    a[k++] = left[i++];
   } else {
    a[k++] = right[j++];
   }
  }

  // Just in case if any sub array is left over
  // with additional elements
  while (i < leftArrItems) {
   a[k++] = left[i++];
  }
  while (j < rightArrItems) {
   a[k++] = right[j++];
  }

 }