quick_sort.cpp

static int split(std::vector<int>& data, const int beg, const int end)
{
	if (beg >= end || end <= 0)
	{
		return -1;
	}
	int idx = beg;
	const int base = data[end - 1];
	for (int i = beg; i < end; i++)
	{
		if (data[i] < base)
		{
			std::swap(data[i], data[idx]);
			idx++;
		}
	}
	std::swap(data[idx], data[end - 1]);
	return idx;
}

static void quick_sort(std::vector<int>& data, const int beg, const int end)
{
	if (beg >= end - 1)
	{
		return;
	}
	const int mid = beg + (end - beg) / 2;
	const int idx = split(data, beg, end);
	if (idx == -1)
	{
		return;
	}
	quick_sort(data, beg, idx);
	//mid: pass
	quick_sort(data, idx + 1, end);
}

static void sort(std::vector<int>& data)
{
	//quick sort
	{
		quick_sort(data, 0, data.size());
	}
}