Sorting algorithms in OCaml

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.

About these ads

2 thoughts on “Sorting algorithms in OCaml

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s