In c Double Insertion Sort is a variation on Insertion Sort

In c++:

Double Insertion Sort is a variation on Insertion Sort that works from the middle of the array
out. At each iteration, some middle portion of the array is sorted. On the next iteration, take the
two adjacent elements to the sorted portion of the array. If they are out of order with respect to
each other, then swap them. Now, push the left element toward the right in the array so long as
it is greater than the element to its right. And push the right element toward the left in the array
so long as it is less than the element to its left.
The algorithm begins by processing the middle two elements of the array if the array is even. If
the array is odd, then skip processing the middle item and begin with processing the elements to
its immediate left and right.
(a) First, explain what the cost of Double Insertion Sort will be in comparison to standard
Insertion sort, and why. (Note that the two elements being processed in the current
iteration, once initially swapped to be sorted with respect to each other, cannot cross as
they are pushed into sorted position.)
(b) Then, implement Double Insertion Sort, being careful to properly handle both when the
array is odd and when it is even.
(c) Compare its running time in practice against standard Insertion Sort.

Solution

class InsertionSort

{

    /*Function to sort array using insertion sort*/

    void sort(int arr[])

    {

        int n = arr.length;

        for (int i=1; i<n; ++i)

        {

            int key = arr[i];

            int j = i-1;

            /* Move elements of arr[0..i-1], that are

               greater than key, to one position ahead

               of their current position */

            while (j>=0 && arr[j] > key)

            {

                arr[j+1] = arr[j];

                j = j-1;

            }

            arr[j+1] = key;

        }

    }

    /* A utility function to print array of size n*/

    static void printArray(int arr[])

    {

        int n = arr.length;

        for (int i=0; i<n; ++i)

            System.out.print(arr[i] + \" \");

        System.out.println();

    }

    // Driver method

    public static void main(String args[])

    {       

        int arr[] = {12, 11, 13, 5, 6};

        InsertionSort ob = new InsertionSort();       

        ob.sort(arr);

        printArray(arr);

    }

}