Cocktail Shaker Sort

Cocktail shaker sort, also known as bidirectional bubble sort, cocktail sort, shaker sort, ripple sort, shuffle sort, or shuttle sort, is a variation of bubble sort that is both a stable sorting algorithm and a comparison sort. The algorithm differs from a bubble sort in that it sorts in both directions on each pass through the list. This sorting algorithm is only marginally more difficult to implement than a bubble sort, and solves the problem of turtles in bubble sorts. It provides only marginal performance improvements, and does not improve asymptotic performance; like the bubble sort.

									void Swap(int* a, int* b)
{
	*a ^= *b;
	*b ^= *a;
	*a ^= *b;
}

void CocktailSort(int* data, int count)
{
	while (1)
	{
		char flag;
		int start[2] = { 1, count - 1 };
		int end[2] = { count, 0 };
		int inc[2] = { 1, -1 };

		for (int it = 0; it < 2; ++it)
		{
			flag = 1;

			for (int i = start[it]; i != end[it]; i += inc[it])
			{
				if (data[i - 1] > data[i])
				{
					Swap(data + i - 1, data + i);
					flag = 0;
				}
			}

			if (flag)
				return;
		}
	}
}

Example

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

Output