MergeSort.java

package com.geeksforgeeks.array;

import com.competitive.coding.spoj.InversionCount;

public class MergeSort
{
  public static void main( String[] args )
  {
    int[] sample = {-12, 11, -13, -5, 6, -7, 5, -3, -6};
//    int[] sample = {2, 4, 1, 3, 5};
//    int[] sample = {1, 20, 6, 4, 5};
    System.out.println( "Inversion Count is " + mergeSort( sample, 0, 4 ) );
    System.out.println( "After sorting is " );
    ArrayRotation.printArray( sample );

  }


  public static int mergeSort( int[] arr, int low, int high )
  {
    int inversionCount = 0;
    if( low < high )
    {
      int mid = low + (high - low) / 2;

      inversionCount = mergeSort( arr, low, mid );
      inversionCount += mergeSort( arr, mid + 1, high );
      inversionCount += merge1( arr, low, mid, high );
    }
    return inversionCount;
  }

  // My Own Implementation + to handle Inversion Count as well
  private static int merge1( int[] arr, int low, int mid, int high )
  {
    int inversionCount = 0;
    int t1 = low;
    int t2 = mid + 1;
    int N1 = mid;
    int N2 = high;
    int[] sortedArr = new int[(high - low) + 1];
    int sortedCounter = 0;
    while( t1 <= N1 && t2 <= N2 )
    {
      if( arr[t1] <= arr[t2] )
      {
        sortedArr[sortedCounter++] = arr[t1++];
      }
      else
      {
        sortedArr[sortedCounter++] = arr[t2++];

        // if arr[t1] > arr[t2] then there at total of Middle - t1 inversions.
        // as till t1 to middle is already sorted, So if arr[t1] > arr[t2] i.e. arr[t+1.....mid] > arr[t2]
        // So those many inversions
        inversionCount += mid + 1 - t1;
      }
    }

    // Let's check whether either of t1 and t2 is still left
    while( t1 <= N1 )
    {
      sortedArr[sortedCounter++] = arr[t1++];
    }

    while( t2 <= N2 )
    {
      sortedArr[sortedCounter++] = arr[t2++];
    }

    // Let's replace sortedArray values into original array
    for( int i = 0; i < sortedArr.length; i++ )
    {
      arr[low++] = sortedArr[i];
    }
    return inversionCount;
  }

  private static void merge( int[] arr, int low, int mid, int high )
  {
    int t1 = low;
    int t2 = mid + 1;
    int[] sortedArray = new int[arr.length];
    int counter = 0;

    while( t1 <= mid && t2 <= high )
    {
      if( arr[t1] < arr[t2] )
      {
        sortedArray[counter++] = arr[t1];
        t1++;
      }
      else if( arr[t2] < arr[t1] )
      {
        sortedArray[counter++] = arr[t2];
        t2++;
      }
    }

    while( t1 <= mid )
    {
      sortedArray[counter++] = arr[t1++];
    }

    while( t2 <= high )
    {
      sortedArray[counter++] = arr[t2++];
    }
    counter = 0;
    for( int i = low; i <= high; i++ )
    {
      arr[i] = sortedArray[counter++];
    }
  }
}