Sorting possible using size 3 subarray rotation

Sorting possible using size 3 subarray rotation

Given an array of integer values which need to be sorted by only one operation – subarray rotation where subarray size should be 3. For example, If our array is (1 2 3 4) then we can reach to (1 4 2 3), (3 1 2 4) in one step. We need to tell whether it is possible to sort the complete array with this operation or not.

Suppose we have one subarray as [A[i] A[i+1] A[i+2]]. After one rotation, we get [A[i+2], A[i], A[i+1]]
If we observe inversions before and after rotation, we can see that parity of inversion is not changed i.e. if [A[i] A[i+1] A[i+2]] has even number of inversions [A[i+2] A[i] A[i+1]] will have even inversions. Same is true for odd inversions. Due to movement of A[i+2], inversions either increase by 2 or decrease by 2 or remain same i.e. their parity won’t change.
After observing above fact we can say that if initial array configuration has even number of inversion then it is possible to make them zero making array completely sorted otherwise not. We use merge sort based method for counting inversions. After getting the number of inversions, we can easily check parity of inversion and conclude whether it is possible to sort the array or not.

    /* This function merges two sorted arrays and

    returns inversion count in the arrays.*/

    public static int merge(int[] arr, int left, int mid, int right)

    {

        int[] temp = new int[arr.length];

        int inv_count = 0;

        int i = left; /* i is index for left subarray*/

        int j = mid; /* j is index for right subarray*/

        int k = left; /* k is index for resultant merged

                         subarray*/

         

        while((i <= mid-1) && (j <= right))

        {

            if(arr[i] <= arr[j])

            {

                temp[k++] = arr[i];

                i++;

            }

            else

            {

                temp[k++] = arr[j];

                j++;

                 

                /* this is tricky -- see above

                explanation/diagram for merge()*/

                inv_count = inv_count + (mid-i);

            }

        }

         

        /* Copy the remaining elements of left subarray

        (if there are any) to temp */

        while(i <= (mid-1))

            temp[k++] = arr[i++];

         

        /* Copy the remaining elements of right subarray

        (if there are any) to temp*/

        while(j <= right)

            temp[k++] = arr[j++];

          

        /* Copy back the merged elements to original

        array */   

        for (int l = left; l <= right; l++)

            arr[l] = temp[l];

  

        return inv_count;

    }

     

    /* An auxiliary recursive function that sorts

    the input array and returns the number of

    inversions in the array. */

    public static int _mergeSort(int[] arr, int left, int right)

    {

        

       int mid, inv_count = 0;

       if(left < right)

       {

            

            /* Divide the array into two parts and

            call _mergeSortAndCountInv() for each

            of the parts */

            mid = (left + right)/2;

            

            /* Inversion count will be sum of inversions

            in left-part, right-part and number of

            inversions in merging */

            inv_count = _mergeSort(arr, left, mid);

            inv_count += _mergeSort(arr, mid+1, right);

            

            inv_count += merge(arr, left, mid+1, right);

            

        }

       return inv_count;

        

   }

     

    /* This function sorts the input array and returns the

    number of inversions in the array */

    public static int mergeSort(int[] arr, int N)

    {

     

        return _mergeSort(arr, 0, N-1);

    }

     

    public static boolean possibleSortingBy3SizeSubarray(int arr[], int N)

    {

        int numberOfInversion = mergeSort(arr, N);

  

        // if number of inversions are even then only

        // we can sort the array

        return (numberOfInversion % 2 == 0);

    }