Basic sorting

A very simple sorting algorithm is bubblesort: 

keep making passes through the array until it is sorted
on each pass
   tentatively mark the array as sorted
   compare each array element with the element after it
   if they are out of order then swap them
      and note that the array wasn't sorted
if you get through an entire pass without swapping anything
   then the array must really be sorted
While simple to implement, bubblesort is very inefficient for large arrays if there are many small values that are far out of place (since each one only moves one spot on each entire pass through the array - whereas large values are likely to move many spots on each pass through the array).

Comb sort is a variation of bubblesort where, instead of comparing each element with the one next to it, we compare each element with something a further distance up the array. Thus values that are far out of place jump across this 'gap' early on, and as we make more and more passes we gradually shrink the size of the gap (on the final passes the gap is set to 1 so we compare neighbours and ensure everything winds up in the exact right spot).

Bubblesort and combsort are illustrated in the comb.C code. 
void swap(long &x, long &y)
{
   long t = x;
   x = y;
   y = t;
}

// keep making passes through the array until it is sorted
// on each pass
//    tentatively mark the array as sorted
//    compare each array element with the element after it
//    if they are out of order then swap them
//       and note that the array wasn't sorted
// if you get through an entire pass without swapping anything
//    then the array must really be sorted
void bubblesort(long *arr, long size)
{
   if (arr == NULL) {
      printf("Cannot sort NULL array\n");
   } else {
      for (int p = 1; p < size; p++) {
          bool sorted = true;
          for (int i = 1; i < size; i++) {
              if (arr[i] < arr[i-1]) {
                 swap(arr[i], arr[i-1]);
                 sorted = false;
              }
          }
          if (sorted) break;
      }
   }
}

// comb sort: like bubblesort except:
//    compares elements across large segments of the array (gaps)
//    gradually shrinks the size of the gap down to 1
// (better than bubblesort at getting rid of small values
//  near the high end of the array, which force near worst
//  case behaviour for bubblesort)    
void combsort(long *arr, long size)
{
   long gap = size;
   bool swapped = false;

   // keep sorting until you've made a pass
   //    with a gap size of 1 where nothing 
   //    out of order was found
   while ((gap > 1) || swapped) {

      // shrink the size of the gap towards 1
      if (gap > 1) gap = (4*gap)/5;

      // check each element pair across the gap
      swapped = false;
      for (int i = 0; (i+gap) < size; i++) {
          if (arr[i] > arr[i+gap]) {
             swap(arr[i], arr[i+gap]);
             swapped = true;
          }
      }
   }
}