Data Structures & Algorithms is an OpenGL visualization of tree data structures and sort algorithms, licensed under GPL.
This is a simple program for visualizing a few different tree datastructures and sorting algorithms, using OpenGL, SDL and SDL_ttf. The program can be used without a gui, but Gtk+, Win32 and Cocoa guis are available. The source code can be compiled on Linux, Windows (using MinGW at least) and OS X.
It should compile quite well out of the box on Linux (assuming development packages for OpenGL, SDL, SDL_ttf and Gtk+ are installed), but the makefiles for MinGW and OS X might need some environment specific tuning.
The execution time for the different algorithms might not be comparable, everything depends on how long animations are used for different operations. But in practice they do show the efficiency differences roughly.
Most algorithms are implemented according to Mark Allen Weiss' Data Structures & Algorithm Analysis in Java.
The optimized merge sort is a slightly modified version of ordinary merge sort, which only needs half the extra memory compared to the original algorithm. This seems to be a bit faster, too. The first of the two subarrays to be merged is copied to the temporary space, and they are merged into the correct destination directly.
Quicksort doesn't use any cutoff, for clarity.
The BST with presorting works by first sorting the input elements. Afterwards, they are inserted with a recursive method, by adding the middle element of a subarray to the tree using completely ordinary methods. Then the left and right subarrays are added recursively. This results in a balanced tree.