Three versions

"Things should be kept as simple as possible but not simpler than that."

[Albert Einstein]

1. This version needs a seperate method

int shiftVacant(Element[] E, int vacant, int x)
{
	while (vacant > 0)
	{
		if (E[vacant - 1].key <= x) return vacant;
		// else
		E[vacant] = E[vacant - 1];
		vacant --;
	}
	return 0;
}

2. This version doesn't need a separate method and may be used in-line; it uses the "short-circuit and"

// int shiftVacant(Element[] E, int vacant, int x)
{
	while ((vacant > 0) && (E[vacant - 1].key > x))
	{
		E[vacant] = E[vacant - 1];
		vacant --;
	}
//	return vacant;
}

3. A recursive version for enthusiasts

int shiftVacant(Element[] E, int vacant, int x)
{
	if (vacant == 0) return 0;
	// else
		if (E[vacant - 1].key <= x) return vacant;
		// else
		E[vacant] = E[vacant - 1];
		return shiftVacant(E, vacant - 1, x)
}