Insertion Sort

How it Works;
0) Sorted data will be at the front of the array, starting 1 place after the start of the data,
1) take your current value out of the array, creating an empty point
2) set your insertion point to the tail of the sorted data.
3a) if the current item is lower then the insertion point item move the insertion points item up to the empty place in the array repeat with the next possible insertion point
3b) if the current item is equal to or greater than the insertion point place the current item back into the arrays empty place and repeat from 1 with the next unsorted data.

Properties;
Worst and average case speed is O(n^2)
Memory is 1
It is Stable (unless you implement it badly)

//compile with g++
#include <iostream>
#include <iomanip>
using namespace std;

void print(int data[], int size);

void insertionSort(int data[], int size)
{
  int tmp;
  int i;
  for(int j = 1; j < size; j++)
    {
      tmp = data[j];
      i = j;
      while(
            (i > 0) &&
            (data[i-1] > tmp)
            )
        {
          data[i] = data[i-1];
          i--;
        }

      if(i != j)
        data[i] = tmp;
    }
}

//test
#define SIZE 20
#define SCRAMBLE(x, y) ((0xa57b & ~y) + ((0x3829 & x) << 1))

bool check(int data[], int size)
{
  for(int i = 1; i < size; i++)
    if(data[i] < data[i-1])
      {
        cout << "FAIL!" << endl;
        return false;
      }
  cout << "PASS" << endl;
  return true;
}

void print(int data[], int size)
{
  for(int i = 0; i < size; i++)
    cout << setw(5) << data[i] << " ";
  cout << endl;
}

bool test(int data[], int size)
{
  print(data, SIZE);
  insertionSort(data,SIZE);
  print(data, SIZE);
  return check(data, SIZE);
}

int main()
{
  int data[SIZE];
  bool pass = true;

  //easy data
  data[0] = 1;
  for(int i = 0; i < SIZE; i++)
    data[i] = SIZE - i;
  pass &= test(data, SIZE);

  //semi repeated data
  data[0] = 1;
  for(int i = 1; i < SIZE; i++)
    data[i] = SCRAMBLE(i, data[i-1]);
  pass &= test(data, SIZE);

  //the sort killer!
  for(int i = 0; i < SIZE; i++)
    data[i] = 5;
  pass &= test(data, SIZE);

  //and some randoms to catch anything i missed
  srand ( time(NULL) );

  for(int j = 0; j < 100; j++)
    {
      for(int i = 0; i < SIZE; i++)
        data[i] = (int)((float)(j+1)*((float)rand()/(float)RAND_MAX));
      pass &= test(data, SIZE);
    }

  if(pass)
    cout << "ALL PASSED" << endl;
  else
    cout << "FAILED" << endl;
}