We had a mini snow storm in Montreal this weekend, so instead of going to my usual Saturday afternoon chess club, I spent the day writing sorting algorithms in OCaml. It had been a while since I’d revised my notes from my algorithms class (which I finished two years ago), and I thought it’s be a nice time to do some review.
I implemented the following algorithms:
- Bubble sort, O(n^2)
- Selection sort, O(n^2)
- Insertion sort, O(n^2)
- Merge sort, O(n lg n)
- Quick sort, O(n lg n)*
* Pivots are chosen at random.
I also wrote a small driver program to test them all on bunch of arrays. Here’s a sample run:
$ ./bench.native --iters 250 --max-elems 2500 100.00% Algorithm : Total Average ============================================================ insertion sort : 2.142468 0.008570 bubble sort : 5.517859 0.022071 selection sort : 2.795310 0.011181 merge sort : 0.115057 0.000460 merge sort + selection sort : 0.100913 0.000404 merge sort + insertion sort : 0.098223 0.000393 quicksort 1 : 0.098276 0.000393 quicksort 2 : 0.090065 0.000360 Array.sort : 0.106113 0.000424 Array.stable_sort : 0.071891 0.000288
(The times are in seconds.)
A few notes: I have implemented an second merge sort function that can use an alternate sorting function when the arrays get small enough. Quicksort 1 and quicksort 2 are both implementations of an in-place Quick sort, but using different implementations. Finally, Array.sort and Array.stable_sort are OCaml’s standard library’s sorting functions.
During the implementation, I realized (again) that merge sort is my favorite sorting algorithm; the idea is simple, the implementation is easy (both with arrays and linked lists) and offers good performance. Insertion sort, which is super easy for linked lists, is a trickier than the other O(n^2) algorithms, because one of the invariants is a little unnatural; the element should be inserted not at position i, but i+1. It makes sense, but I was caught when I initially wrote the code, and ended up with an incorrect algorithm.
Notably missing from the list of algorithms are heapsort (which I’ll hopefully implement this week) and newer algorithms such as timsort and introsort, which I know little about.
I have made my code available on Github if you wish to look at it; I would also love to get some input on the quality of the code, or how to improve my code.