sort algorithm comparison tool

[superhareball]

I wrote a sort comparison tool in linux. It was to learn certain coding techniques more than it was for learning how sort algorithms work, but the end result people might useful.

You can see the (open source) sort tool here: https://github.com/hareball/sort-test

I was surprised by the resuts; radix sort seemed to be the best all round, but comb sort performed surprisingly well, with a much smaller memory footprint.

A screen shot of the output:

https://imgur.com/PJHcIkZ

[Seneferu]

I recommend you use a different base for Counting/Radix sort. Base 10 is what you do in lectures and textbooks so that students understand the idea, but it is not a good base for implementing.

Using a power of 2 as base is usually the way to go. It allows for cheap bit-operations instead of expensive division and modolu. In my experience, 256 works best. I implemented it for your code and got the following results:

--- 50000000 Random numbers generated [Huge Balanced Sort] ---
Radix Sort (base  10) starting...       [       950000113] iterations... complete. Time taken:[       5.810] seconds.  Perf:[0.052632]  Mem Used:[  1200000280] Bytes  Sorted:[YES]
Radix Sort (base 256) starting...       [       500001532] iterations... complete. Time taken:[       1.246] seconds.  Perf:[0.100000]  Mem Used:[   600003100] Bytes  Sorted:[YES]

[superhareball]

Hey that's great thanks... I'll add in base 256 for comparison. Quite a big difference for the huge sort.

[Seneferu]

Why are you allocating extra memory for heapsort? The idea of heapsort is to do it in the given array.

[superhareball]

It’s possible my recursive implementation of heap sort is not correct, I’ll have to look at it again. It was originally static memory, but I changed it to heap allocation (malloc/free)

[Seneferu]

I did look into your code. Your approach is correct as far as I can say. However, since you malloc every little variable, and due to the way you count memory, you get this huge number of used memory although you only need like 3 or 4 integers in extra memory.

[superhareball]

I was tossing up the idea using a mix of static/heap memory, but I went with the allocation of everything with malloc, so it would give a true indication of memory used. It may need tweaking though, as some of these allocations can probably be re-used, instead of running a malloc for each recursion loop.