Straight Insertion Sort

Primary Variables:

curr_spot = location of the next value to be moved

insert_spot = location of where to insert the next value being moved

value = the value being inserted

last = the index of the last element of the array, i.e. size-1

   for each element in the list
      remember the value being moved
      while value is not in its correct place
         move elements to the right
      put value in its new spot

C++ Code

curr_spot = 1
while (curr_spot <= last)
  {
   value  = list[curr_spot];
   insert_spot = curr_spot – 1;
   while (insert_spot >= 0  &&  value < list[insert_spot])
      list[insert_spot + 1] = list[insert_spot]
      insert_spot = insert_spot – 1;
   list [ insert_spot + 1 ] = value;
   curr_spot = curr_spot + 1;
  }

Shell Sort

increment = last/2
while (increment != 0)
  {
   curr_spot = increment;
   while (curr_spot <= last)
    {
     value = list[curr_spot]
     insert_spot = curr_spot – increment
     while (insert_spot >=0  &&  value < list[insert_spot])
        list[insert_spot + increment] = list[insert_spot]
        insert_spot = insert_spot – increment
     list[insert_spot + increment] = value
     curr_spot = curr_spot + 1
    }
   increment = increment / 2
  }