#define swap(x,t,y) do { t=x; x=y; y=t; } while(0)

void inplace_merge(int numbers[], int count)
{
	int split, join, size, actualsize, t;
	int left, middle, offset, leftwidth, i;
        //sort pairs
	for (split = 0; split < count; split += 2)
	{
		if (split < count-1)
			if (numbers[split] > numbers[split+1])
				swap(numbers[split],t,numbers[split+1]);
	}
        //merge in progressive powers of two
	for (size = 4; size < count*2; size *= 2)
	{
		for (join = 0; join < count; join+=size)
		{
			actualsize = count - join;
			if (actualsize > size)
				actualsize = size;
			offset = 0;
			left = join;
			leftwidth = size/2;
			middle = join+size/2;
                        //the left is a ring buffer, the right (aka middle) is always sorted
			while (left < middle && middle < join+actualsize) {
				if (numbers[left + offset] > numbers[middle])
				{
					swap(numbers[left],t,numbers[middle]);
					middle++;
					offset=(offset - 1 + leftwidth) % leftwidth;
				} else {
                                        //de-ring left
					while (offset)
					{
						if (offset > leftwidth / 2) {
							//Rotate left
							i = leftwidth - 1;
							t = numbers[left + i];
							for (; i; i--)
								numbers[left + i] = numbers[left + i - 1];
							numbers[left] = t;
							offset = (offset + 1) % leftwidth;
						} else {
							//Rotate right
							i = 0;
							t = numbers[left];
							for (i = 0; i < leftwidth - 1; i++)
								numbers[left + i] = numbers[left + i + 1];
							numbers[left + i] = t;
							offset--;
						}
					}
					leftwidth--;
				}
				left++;
			}
                        /* de-ring left (necessary, as the whole right
                         * could have been moved to the left
                         */
			while (offset)
			{
				if (offset > leftwidth / 2) {
					//Rotate left
					i = leftwidth - 1;
					t = numbers[left + i];
					for (; i; i--)
						numbers[left + i] = numbers[left + i - 1];
					numbers[left] = t;
					offset = (offset + 1) % leftwidth;
				} else {
					//Rotate right
					i = 0;
					t = numbers[left];
					for (i = 0; i < leftwidth - 1; i++)
						numbers[left + i] = numbers[left + i + 1];
					numbers[left + i] = t;
					offset--;
				}
			}
		}
	}
}