Some programming junk food. Felt like implementing a parallel quicksort and was baffled at how fast it is.

sorting.d

import std.stdio;

import std.traits : isOrderingComparable;

import std.range;

import std.algorithm.sorting;

import std.algorithm.mutation;

import std.typecons : Nullable;

import std.parallelism : totalCPUs;

auto parallelQuicksort(T)(T[] list,uint maxThreads = totalCPUs)
	if(isOrderingComparable!T)
{
	if(list.length < 64 || maxThreads <= 1)
	{
		return sort(list);
	}
	import std.parallelism : scopedTask, taskPool;
	auto pieces = partition3(list,list[$/2]);
	auto right = scopedTask!parallelQuicksort(pieces[2],maxThreads/2);
	right.executeInNewThread();
	parallelQuicksort(pieces[0],maxThreads/2);
	right.workForce();
	return assumeSorted(list);
}

auto moreParallelQuicksort(T)(T[] list)
	if(isOrderingComparable!T)
{
	if(list.length < 64)
	{
		return sort(list);
	}
	import std.parallelism : scopedTask, taskPool;
	auto pieces = partition3(list,list[list.length/2]);
	auto leftSorted = scopedTask!moreParallelQuicksort(pieces[0]);
	auto rightSorted = scopedTask!moreParallelQuicksort(pieces[2]);
	taskPool.put(leftSorted);
	taskPool.put(rightSorted);
	leftSorted.workForce();
	rightSorted.workForce();
	return assumeSorted(list);
}

auto insertionSort(T)(T[] list)
	if(isOrderingComparable!T)
{
	foreach(i;1..list.length)
	{
		auto j = i;
		while(j>0 && list[j-1] > list[j])
		{
			list.swapAt(j,j-1);
			j -= 1;
		}
	}
	return assumeSorted(list);
}

void justQuicksort4Head(T)(T[] list, T likelyMin, T likelyMax)
{
	if(list.length < 64)
	{
		sort(list);
	}
	if(list.length < 512)
	{
		import std.algorithm.searching : minElement,maxElement;
		likelyMin = minElement(list);
		likelyMax = maxElement(list);
	}
	import std.parallelism : scopedTask, taskPool;
	auto pieces = partition3(list,(likelyMin+likelyMax)/2);
	auto leftSorted = scopedTask!moreParallelQuicksort(pieces[0]);
	auto rightSorted = scopedTask!moreParallelQuicksort(pieces[2]);
	taskPool.put(leftSorted);
	taskPool.put(rightSorted);
	leftSorted.workForce();
	rightSorted.workForce();
}

auto sortWithInfo(T)(T[] list,T likelyMin,T likelyMax)
{
	import std.parallelism : parallel;
	import std.math : abs;
	list.justQuicksort4Head(likelyMin,likelyMax);
	return assumeSorted(list);
}

int slightlyTweak(int a)
{
	import std.random : uniform;
	return a + uniform!"[]"(-10,10);
}

int slightlyTweakAndSquash(int a)
{
	import std.random : uniform;
	return (a/100) + uniform!"[]"(-1,1);
}

mixin template SortingAlgoTest(alias func)
{
	unittest
	{
		import std.array : array;
		import std.range : generate, takeExactly;
		import std.random : uniform;
		import core.time : MonoTime,dur;
		writeln(__traits(identifier,func),":");
		long rollingAverage = 0;
		auto averagedSoFar = 0;
		foreach(i;0..3)
		{
			int[] arr = generate!(() => uniform(-10000000, 10000000)).takeExactly(10000000).array;
			immutable auto start = MonoTime.currTime;
			func(arr);
			immutable auto thisTime = (MonoTime.currTime - start).total!"hnsecs";
			foreach(idx;1..arr.length)
			{
				import std.conv : to;
				immutable int prev = arr[idx-1];
				immutable int curr = arr[idx];
				assert(prev <= curr,"Not sorted! Index "~idx.to!string~" is "~curr.to!string~", less than "~prev.to!string);
			}
			rollingAverage = (thisTime + (rollingAverage * averagedSoFar))/(averagedSoFar+1);
			averagedSoFar++;
		}
		writeln("Random array (huge range): ",dur!"hnsecs"(rollingAverage));
		rollingAverage = 0;
		averagedSoFar = 0;
		foreach(i;0..3)
		{
			int[] arr = generate!(() => uniform(-100, 100)).takeExactly(1000000).array;
			immutable auto start = MonoTime.currTime;
			func(arr);
			immutable auto thisTime = (MonoTime.currTime - start).total!"hnsecs";
			assert(isSorted(arr));
			rollingAverage = (thisTime + (rollingAverage * averagedSoFar))/(averagedSoFar+1);
			averagedSoFar++;
		}
		writeln("Random array (many duplicates): ",dur!"hnsecs"(rollingAverage));
		{
			import std.range : iota;
			int[] arr = iota(500000,-500000,-1).array;
			immutable auto start = MonoTime.currTime;
			func(arr);
			writeln("Reversed array: ",MonoTime.currTime - start);
			assert(isSorted(arr));
		}
		{
			import std.range : iota;
			import std.parallelism : taskPool;
			int[] arr = taskPool.amap!slightlyTweak(iota(-500000,500000,1),100000).array;
			immutable auto start = MonoTime.currTime;
			func(arr);
			writeln("Nearly sorted: ",MonoTime.currTime - start);
			assert(isSorted(arr));
		}
		{
			import std.range : iota;
			import std.parallelism : taskPool;
			int[] arr = taskPool.amap!slightlyTweakAndSquash(iota(-500000,500000,1),100000).array;
			immutable auto start = MonoTime.currTime;
			func(arr);
			writeln("Nearly sorted (many duplicates): ",MonoTime.currTime - start);
			assert(isSorted(arr));
		}
	}
}

mixin SortingAlgoTest!parallelQuicksort;

mixin SortingAlgoTest!moreParallelQuicksort;

unittest // this one takes function arguments, so it needs its own test, natch
{
	import std.array : array;
	import std.range : generate, takeExactly;
	import std.random : uniform;
	import core.time : MonoTime,dur;
	writeln(__traits(identifier,sortWithInfo),":");
	long rollingAverage = 0;
	auto averagedSoFar = 0;
	foreach(i;0..3)
	{
		int[] arr = generate!(() => uniform(-10000000, 10000000)).takeExactly(10000000).array;
		immutable auto start = MonoTime.currTime;
		sortWithInfo(arr,-10000000,10000000);
		immutable auto thisTime = (MonoTime.currTime - start).total!"hnsecs";
		foreach(idx;1..arr.length)
		{
			import std.conv : to;
			immutable int prev = arr[idx-1];
			immutable int curr = arr[idx];
			assert(prev <= curr,"Not sorted! Index "~idx.to!string~" is "~curr.to!string~", less than "~prev.to!string);
		}
		rollingAverage = (thisTime + (rollingAverage * averagedSoFar))/(averagedSoFar+1);
		averagedSoFar++;
	}
	writeln("Random array (huge range): ",dur!"hnsecs"(rollingAverage));
	rollingAverage = 0;
	averagedSoFar = 0;
	foreach(i;0..3)
	{
		int[] arr = generate!(() => uniform(-100, 100)).takeExactly(1000000).array;
		immutable auto start = MonoTime.currTime;
		sortWithInfo(arr,-100,100);
		immutable auto thisTime = (MonoTime.currTime - start).total!"hnsecs";
		assert(isSorted(arr));
		rollingAverage = (thisTime + (rollingAverage * averagedSoFar))/(averagedSoFar+1);
		averagedSoFar++;
	}
	writeln("Random array (many duplicates): ",dur!"hnsecs"(rollingAverage));
	{
		import std.range : iota;
		int[] arr = iota(500000,-500000,-1).array;
		immutable auto start = MonoTime.currTime;
		sortWithInfo(arr,-500000,500000);
		writeln("Reversed array: ",MonoTime.currTime - start);
		assert(isSorted(arr));
	}
	{
		import std.range : iota;
		import std.parallelism : taskPool;
		int[] arr = taskPool.amap!slightlyTweak(iota(-500000,500000,1),100000).array;
		immutable auto start = MonoTime.currTime;
		sortWithInfo(arr,-500000,500000);
		writeln("Nearly sorted: ",MonoTime.currTime - start);
		assert(isSorted(arr));
	}
	{
		import std.range : iota;
		import std.parallelism : taskPool;
		int[] arr = taskPool.amap!slightlyTweakAndSquash(iota(-500000,500000,1),100000).array;
		immutable auto start = MonoTime.currTime;
		sortWithInfo(arr,-5000,5000);
		writeln("Nearly sorted (many duplicates): ",MonoTime.currTime - start);
		assert(isSorted(arr));
	}
}

mixin SortingAlgoTest!sort;