Arne Maus' Sorting home page (latest update November 2015)

This page presents seven original sorting algorithms (+ variants) in Java designed by Arne Maus.
All algorithms are downloadable and their usage are regulated by the BSD license
(basically that their original author must always be credited whenever used).
All code is accompanied by a pubished paper explaining its usage, performance and limitations.
Disclaimer: Although all these algorithms are thoroughly tested, no guarantee is given that they
work as intended in any application where they might be used.

The algorithms

All code (in Java) have a small test program in 'main' so you can test the algorithms . These algorithms are, like almost all memory intensive algorithms, rather sensitive for the number of caches on the CPU and their speed relative to main memory; as demonstrated in this paper. All these algorithms operate on integer array with n non-negative numbers.
Let M be the largest element in the array, and b be the maximum number of bits in any sorting digit (tunable). Code is also in some cases given for handling a mixture of positive and negative numbers, but this handling is always done in a pre-processing, interfacing method, this is generally avoided to concentrate on the algorithms.

Paper, the effects of caching on sorting

This paper shows that it pays to tune our algorithms to the underlying hardware, especially to the size of the largest cache. It is demonstrated how three times as many instructions performed may be five times as fast in practical Radix based sorting.when the array is much larger the the largest cache.
  • Arne Maus and Stein Gjessing:
    Latest update 19. November 2015 (soon to be published: Effective sequential and parallel ShellSort).