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.



									public static void InsertionSort(ref int[] data)
{
	for (int i = 1; i < data.Length; ++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 = new int[] { -1, 25, -58964, 8547, -119, 0, 78596 };
InsertionSort(ref data);
								


Output

									-58964
-119
-1
0
25
8547
78596