Insertion Sort

Insertion sort is a sorting algorithm that builds the final sorted array one item at a time. It works the way we sort playing cards in our hands. It is much less efficient on large lists than more advanced algorithms such as Quick sort, Heap sort, or Merge sort.



									static void InsertionSort(int* data, int count) {
	for (int i = 1; i < count; ++i)
	{
		int j = i;

		while ((j > 0))
		{
			if (data[j - 1] > data[j])
			{
				data[j - 1] ^= data[j];
				data[j] ^= data[j - 1];
				data[j - 1] ^= data[j];

				--j;
			}
			else
			{
				break;
			}
		}
	}
}
								


Example

									int data[] = { -1, 25, -58964, 8547, -119, 0, 78596 };
InsertionSort(data, 7);
								


Output

									-58964
-119
-1
0
25
8547
78596