Insertion-Sort with running time O(n lg(n))

Insertion Sort :
Insertions sort , sorts the elements in place in an array with running time O(n2).
Below is code of insertion sort with running time O(n2) :


void InsertionSort(vector<int>& aV)
{
int size = aV.size();
for(int i=1;i<size;i++)
 {
  for(int j=0;j<i;j++)
   {
     // Places element i in correct and sorted sub-array 0...(i-1)
     if(aV[i]<aV[j])
     {
      int temp = aV[i]; 
      aV[i]=aV[j];
      aV[j]=temp;
     }
   }
 }
}

Here we can play with above code to improve running time to O(n lg(n)) by using Binary Search.

Instead of inner loop in code mentioned above , Binary Search can be used to search for place of swap and then sort remaining array so that sub-array ( from 0 to (i-1) ) will be sorted.

Please find code below :

/*Insertion Sort with Binary Search Running time : O(n lg(n)) */

void BinarySearchAndSwap(vector<int> &aV,int aIndexTillSorted,int aIndexToSearch)

{

int low =0;

int high =  aIndexTillSorted;

    while(low<=high)

         {

          int mid = (low+high)/2;

          if(aV[mid]>aV[aIndexToSearch])

          {

           if(aV[mid-1]>aV[aIndexToSearch])

              high = mid-1;

           else // swap mid and aIndexToSearch

               {

                int temp = aV[aIndexToSearch];

                aV[aIndexToSearch] = aV[mid];

                aV[mid]= temp;

                // To sort remaining part of array 

                  low= mid+1;

               }   

          

          }else if(aV[mid]<aV[aIndexToSearch])

          {

           if(aV[mid +1]< aV[aIndexToSearch])

               low = mid+2;

           else{ // Swap mid +1 with aIndexToSearch

                int temp = aV[aIndexToSearch];

                aV[aIndexToSearch] = aV[mid +1];

                aV[mid+1] = temp;

                // To sort remaining part of array 

                low= mid+2;         

                }    

          }        

             

             

          }

}

void InsertionSortWithbinarySearch(vector<int> &aV)

{

int size = aV.size();

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

    {

     BinarySearchAndSwap(aV,i-1,i);

    }

}