Sorting & Searching Experimentarium

The C/C++ programs reported on this page have been written by Svante Carlsson (Luleå University of Technology), Jyrki Katajainen (University of Copenhagen), Tomi Pasanen (University of Turku), and Jukka Teuhola (University of Turku). You can redistribute the programs and/or modify them under the terms of the GNU General Public License. There is no warranty for the programs. If you have comments concerning the programs, do not hesitate to contact the authors of the corresponding research paper.

In-place sorting

J. Katajainen, T. Pasanen, and J. Teuhola, Practical in-place mergesort, Nordic Journal of Computing 3 (1996) 27-40.

Integer sorting programs (the MIX model):

• In-Place 2-Way Mergesort
• In-Place 4-Way Mergesort
• In-Place 4-Way Mergesort where the selection tree is replaced by an array of size 4.
• Standard Mergesort
• Bottom-Up Heapsort

Polymorphic sorting programs (the qsort model):

• In-Place 2-Way Mergesort
• In-Place 4-Way Mergesort
• In-Place 4-Way Mergesort where the selection tree is replaced by an array of size 4.
• Standard Mergesort
• Bottom-Up Heapsort

This header file defines the necessary macros to count the number of comparisons and assignments performed.

Distributive sorting

S. Carlsson, J. Katajainen, and J. Teuhola, In-place linear probing sort, DIKU Report 92/3, Department of Computer Science, University of Copenhagen (1992).

• Linear Probing Sort as described in [G. H. Gonnet & R. Baeza-Yates: Handbook of Algorithms and Data Structures, 2nd Edition, Addison-Wesley Publishing Company, 1991].
• In-place Linear Probing Sort
• Adaptive In-place Linear Probing Sort
• Bucketsort as described in [G. H. Gonnet & R. Baeza-Yates: Handbook of Algorithms and Data Structures, 2nd Edition, Addison-Wesley Publishing Company, 1991], where it was called Interpolation Sort.
• Quicksort adapted from the Pascal program given in [G. H. Gonnet & R. Baeza-Yates: Handbook of Algorithms and Data Structures, 2nd Edition, Addison-Wesley Publishing Company, 1991].
• Bottom-Up Heapsort
• This testbed gives you an opportunity to test the performance of these sorting programs on your own machine.