Insertion Sort

Background:

https://en.wikipedia.org/wiki/Sorting_algorithm

Insertion sort and selection sort are quite similar.
http://en.wikipedia.org/wiki/Insertion_sort

http://en.wikipedia.org/wiki/Selection_sort

'Among simple average-case Θ(n²) algorithms, selection sort almost always outperforms bubble sort and gnome sort. Insertion sort is very similar in that after the kth iteration, the first k elements in the array are in sorted order. Insertion sort's advantage is that it only scans as many elements as it needs in order to place the k + 1st element, while selection sort must scan all remaining elements to find the k + 1st element.'

As its name suggests, it's a sort to be used while elements are being inserted into the array (or vector or whatever it is you're using), or sometimes when the array is "almost sorted". For an unsorted array, it's better to use quick sort or merge sort if it needs to be stable. Note, however, that insertion sort is actually faster when sorting while inserting.

http://mathbits.com/MathBits/CompSci/Arrays/Insertion.htm

http://www.programiz.com/article/insertion-sort-algorithm-programming

http://see.stanford.edu/materials/icspacs106b/Lecture15.pdf

Intuitively, inserting into a list is easier than inserting into an array as one has to move the elements in an array that are bigger than cur to the right. In terms of implementation, insertion sort an array compares from cur back as j-- till head of the array, while insertion sort a list compares from the head of the list and proceed down the list till end of the list.

1. Sort an array using insertion sort.
  void InsertionSort(vector<int> &v)
 {
       int j, len = v.size();
       for (int i = 1; i <len; i++)
       {
              int cur = v[i];
             // Slide cur down into position to left,
            // and move all the elements bigger than cur to be one more position to the right
              for (j = i - 1; j >= 0 && v[j]>cur; j--)
             {
                   v[j + 1] = v[j];
              }
              v[j+1] = cur;
        }
 }


2. Sort a linked list using insertion sort.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        if (head==NULL||head->next==NULL) return head;
        ListNode *ret=NULL;
       
        ListNode *cur;
       
        while(head!=NULL)
        {
            cur = head;
            head = head->next;

           // insert into the head of the sorted list
            // or as the first element into an empty sorted list
            if (ret==NULL||cur->val< ret->val)
            {               
                cur->next = ret;
                ret = cur;
            }
            else
            {
                // insert current element into proper position in non-empty sorted list
                ListNode *p = ret;
                while(p!=NULL)
               {
                  if (p->next==NULL||cur->val<p->next->val)
                  {
                     // insert into middle of the sorted list or as the last element
                    cur->next = p->next;
                    p->next = cur;
                    break;
                  }
                p=p->next;
               }
            }
        }       
        return ret;       
    }
};