Sort.h

#pragma once

#include "sf/Base.h"
#include "sf/Array.h"

namespace sf {

// -- Slice

struct ImpSortRange
{
	void *left, *right;
};

template <typename T, typename Cmp>
void impSort(T *data, size_t size, Cmp cmpFn)
{
	if (size <= 1) return;

	ImpSortRange stack[128], *top = stack;
	T *left = data, *right = data + size - 1;

	uint32_t rng = 0;

	for (;;) {
		sf_assert(left != right);

		if (right - left <= 32) {

			// Insertion sort
			T *hi = left + 1;
			while (hi <= right) {
				if (cmpFn(*hi, hi[-1])) {
					T *lo = hi;
					T tmp(std::move(*hi));
					do {
						lo->~T(); new (lo) T(std::move(lo[-1]));
						lo--;
					} while (lo != left && cmpFn(tmp, lo[-1]));
					lo->~T(); new (lo) T(std::move(tmp));
				}
				hi++;
			}

		} else {

			// Partition
			T *pivot = left + ((right - left) >> 1);
			if (rng) {
				// Xorshift32
				rng ^= rng << 13;
				rng ^= rng >> 17;
				rng ^= rng << 5;
				pivot = left + rng % (right - left);
			}

			T *lo = left - 1;
			T *hi = right + 1;

			for (;;) {
				do lo++; while (cmpFn(*lo, *pivot));
				do hi--; while (cmpFn(*pivot, *hi));
				if (lo >= hi) break;
				impSwap(*lo, *hi);

				if (lo == pivot) pivot = hi;
				else if (hi == pivot) pivot = lo;
			}

			lo = hi;
			if (!cmpFn(*lo, *pivot)) {
				while (lo > left && !cmpFn(lo[-1], *pivot)) --lo;
			}
			if (!cmpFn(*pivot, *hi)) {
				while (hi < right && !cmpFn(*pivot, hi[1])) ++hi;
			}

			size_t limit = ((right - left) >> 2) * 3;
			size_t numLeft = lo - left;
			size_t numRight = right - hi;
			if (rng == 0 && limit > 128 && (numLeft > limit || numRight > limit)) {
				rng = 1;
			}

			if (numLeft > 0) {
				if (numRight > 1) {
					top->left = hi + 1;
					top->right = right;
					top++;

					if (top - stack >= (sf_arraysize(stack) >> 1)) {
						// Transition to heap sort
						right = lo;
						break;
					}
				}
				right = lo;
				continue;
			} else if (numRight > 1) {
				left = hi + 1;
				right = right;
				continue;
			}
		}

		if (top != stack) {
			--top;
			left = (T*)top->left;
			right = (T*)top->right;
		} else {
			// Done!
			return;
		}
	}

	// Heap sort
	for (;;) {
		sf_assert(left != right);

		// No insertion sort here as this code should only be
		// executed for malicious inputs.

		size_t num = right - left + 1;
		size_t start = (num - 1) >> 1;
		size_t end = num - 1;
		for (;;) {

			size_t root = start;
			size_t child;
			while ((child = root*2 + 1) <= end) {
				size_t next = cmpFn(left[child], left[root]) ? root : child;
				if (child + 1 <= end && cmpFn(left[next], left[child + 1])) {
					next = child + 1;
				}
				if (next == root) break;
				impSwap(left[root], left[next]);
				root = next;
			}

			if (start > 0) {
				start--;
			} else if (end > 0) {
				impSwap(left[end], left[0]);
				end--;
			} else {
				break;
			}
		}

		if (top != stack) {
			--top;
			left = (T*)top->left;
			right = (T*)top->right;
		} else {
			// Done!
			return;
		}
	}
}

template <typename T>
sf_inline void sort(sf::Slice<T> data) {
	impSort(data.data, data.size, [](const T &a, const T &b) -> bool {
		return a < b;
	});
}
template <typename T>
sf_inline void sortRev(sf::Slice<T> data) {
	impSort(data.data, data.size, [](const T &a, const T &b) -> bool {
		return b < a;
	});
}

template <typename T, typename Cmp>
sf_inline void sort(sf::Slice<T> data, Cmp cmpFn) {
	impSort(data.data, data.size, [&](const T &a, const T &b) -> bool {
		return cmpFn(a, b);
	});
}
template <typename T, typename Cmp>
sf_inline void sortRev(sf::Slice<T> data, Cmp cmpFn) {
	impSort(data.data, data.size, [&](const T &a, const T &b) -> bool {
		return cmpFn(b, a);
	});
}

template <typename T, typename Key>
sf_inline void sortBy(sf::Slice<T> data, Key keyFn) {
	impSort(data.data, data.size, [&](const T &a, const T &b) -> bool {
		return keyFn(a) < keyFn(b);
	});
}
template <typename T, typename Key>
sf_inline void sortByRev(sf::Slice<T> data, Key keyFn) {
	impSort(data.data, data.size, [&](const T &a, const T &b) -> bool {
		return keyFn(b) < keyFn(a);
	});
}

// -- Array

template <typename T>
sf_inline void sort(sf::Array<T> &data) { return sort(data.slice()); }
template <typename T>
sf_inline void sortRev(sf::Array<T> &data) { return sortRev(data.slice()); }

template <typename T, typename Cmp>
sf_inline void sort(sf::Array<T> &data, Cmp cmpFn) { return sort(data.slice(), cmpFn); }
template <typename T, typename Cmp>
sf_inline void sortRev(sf::Array<T> &data, Cmp cmpFn) { return sortRev(data.slice(), cmpFn); }

template <typename T, typename Key>
sf_inline void sortBy(sf::Array<T> &data, Key keyFn) { return sortBy(data.slice(), keyFn); }
template <typename T, typename Key>
sf_inline void sortByRev(sf::Array<T> &data, Key keyFn) { return sortByRev(data.slice(), keyFn); }

}