Engineering a Cache-Oblivious Sorting Algorithm



Gerth Stølting Brodal, Rolf Fagerberg, and Kristoffer Vinther

A 27-funnel with order 3 basic mergers, as seen from above


All source is released here under the GNU General Public License.


The source can be downloaded here. Please check out the funnelsort project's home page for latest version of the funnelsort implementation. The source is located in directories with the following structure:

Please note that the code is written in ISO98 C++ using concepts such as partial template specialization. Not all compilers support these concepts, though most recent ones do. Using either of the following is recommended:

Quick Start

This section provides a brief introduction to using the source code once downloaded and extracted.

Using the funnelsort implementation

Start by including the merger and sort headers:

		#include <funnel.h>
		#include <sort.h>

Pick a merger to be used by the sort function, say a funnel (denoted a merge_tree) using four-way basic mergers merging arrays of ints:

		typedef typename iosort::merge_tree<int*,4> merger;

Use iosort::merge_sort to sort the int array:

		#include <vector>
		void sort_2k()
			std::vector<int> array(2000);
			// TODO: populate array with input.
			std::vector<int> output(2000);

			iosort::merge_sort<merger,iosort:default_splitter<2> >
				(array.begin(), array.end(), output.begin());

			// output now contains copies of the elements in array in sorted order

or if you prefer

		// C-style:
		#include <stdlib.h>
		void sort_2k()
			int* array = (int*)malloc(2000*sizeof(int));
			// TODO: populate array with input.
			int* output = (int*)malloc(2000*sizeof(int));

			iosort::merge_sort<merger,iosort:default_splitter<2> >
				(array, array+2000, output);

			// output now poitns to copies of the elements in array in sorted order


The iosort:default_splitter class template defines parameters used to decide the order of the merger to use for a given problem size and similar issues.

Using benchmarking programs

cd your way through the benchmarking/bin/ directory locating an architecture and compiler appropiate for you. Once there type make depend followed by make all. The directory will now contain the benchmarking programs and executables for each of the sorting algorithms.

Each of the sorters can be used in two ways: sorting files on disk and sorting arrays in memory. Sorting files is done by first creating a file using sortgen (if benchmarking this should be followed by fillmem to make sure the generated input is not cached) and sorting it using the sorter. Both sortgen and the sorters expect a parameter, -e, specifying the type of elements to generate and sort (i for ints, p for pairs of ints and void*s, and r for 100 byte records). sortgen also needs a -d parameter specifying the type of distribution. Sorting arrays in memory is similar, except instead of providing file names, one provides distribution type and size directly.

All sorters writes identical XML fragments to stdout containing benchmarking data.



Last updated: April 13th, 2005.
See here for latest revision.