Insertion Sort

  1. Create a dummy sorted linked list
  2. take one node from the unsorted linked list and Search Insert Position in the dummy sorted linked list
  3. Insert the node to the Insert Position in the dummy sorted linked list
  4. repeat step 2 until there is no more nodes.