Arne Maus' Sorting home page (latest update August 2018)

This page presents 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.

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. August 2018 .