Insertion Sort on Doubly Linked List

InsertionSort on doubly linked list 

The classes for Doubly linked list are implemented here 

To understand it in better way  take an analogy from arrays insertion sort  -

 see Insertion sort on arrays  here


  for(i = 1  ; i  < array.length ; ++i)
  {
   for( j = i - 1 ; j >= 0 && array[j+1] < array[j] ; --j )
   {
   //swap array[j+1] and array[j]
   }
  
  }
  
  Derving Analogy for doubly linked list from arrays for Insertion sort algo
         DNode pivot - array[i] or array[j+1]
         DNode ins - array[j]
         DNode ins.index - j
 
        while(list.hasPrev(ins) && ins.getData().compareTo(pivot.getData()) > 0 ) -  while(j>=0 and array[j] > array[j+1])
 

public void insertionSort(DblyLinkedList list)
{
//if the size of list is smaller than or equal to one , then its already sorted
if(list.getSize() <= 1)
{
return ;
}

// a pivot node which will be compared everytime with the sorted list 
// to its left to get its proper place in list 
DNode pivot  ;

//insertion point 
DNode ins ; 

//end of run
DNode end  = list.getFirst();

DNode lastNode = list.getLast();

while(end != lastNode)
{

pivot  = end.getNext(); // get the next pivot node , this is the node to be insertion sorted

list.removeNode(pivot); // remove pivot from the list to place it in right order

ins  = end ; // start searching to left from the end of sorted run
while(list.hasPrev(ins) && ins.getData().compareTo(pivot.getData()) > 0 )
{
//loop to left to find appropriate insertion  place for the pivot
ins  = ins.getPrev() ; //move to left
}
list.insertAfter(ins, pivot); // insert the pivot at right place

// if we added pivot just after end of sorted run in this case i.e the pivot
// is already at its right place , increment end marker
if(ins ==  end )  end = end.getNext();
}




}