Function sort

Tools/EditorFramework/pugixml.cpp:6278–6307

template<typename I, typename Pred>
void sort(I begin, I end, const Pred& pred)
{
	// sort large chunks
	while (end - begin > 32)
	{
		// find median element
		I middle = begin + (end - begin) / 2;
		median(begin, middle, end - 1, pred);

		// partition in three chunks (< = >)
		I eqbeg, eqend;
		partition(begin, middle, end, pred, &eqbeg, &eqend);

		// loop on larger half
		if (eqbeg - begin > end - eqend)
		{
			sort(eqend, end, pred);
			end = eqbeg;
		}
		else
		{
			sort(begin, eqbeg, pred);
			begin = eqend;
		}
	}

	// insertion sort small chunk
	if (begin != end)
		insertion_sort(begin, end, pred, &*begin);
}
PUGI__NS_END

// Allocator used for AST and evaluation stacks