Tonight I sat down to do some more work in Chris Pine’s “Learn to Program” book. I’ve been working in it for a couple of weeks now and I find that it’s a good refresher on programming methodology. It’s a bit outdated but it still serves a function for me right now. (I think it was first published in 2004).
I’ve been sailing through the book and all of the exercises and was quite happy with myself; until I got to section 10.2 where I was asked to write my sort method as a “rite of passage.” Obviously, Ruby has it’s own sort method, Array#sort. But never one to ignore a fun challenge I geared up for an interesting evening.
I tried a few things on my own merits but ultimately went searching online for some tips. I came across a beautiful solution (trust me, there were UGLY ones out there) but I couldn’t wrap my newb brain around the logic of it. So I asked Adam to step in and help me decipher what was going on in this code:
As an aside, this stuff takes me awhile to digest because my brain is already pathetically overused by the time I sit down to learn. Between watching Serenity and Sébastien all day, keeping the house in reasonable order, preparing three nutritious meals a day, and everything that happens in between all that I am poached by 8pm when the kids are finally in bed. On top of that, Sébastien still wakes up every hour and a half all night long to nurse, and they both wake up by 5:30-6:00am for the day so I never really sleep; so just add zombie to my list of character traits, along with indecisive, erratic and total_nutcase.
That being said, I definitely asked Adam to sit down with me and help me work through that code. We re-worked it a bit to fit with my data from the exercise, and here is what we have:
It took me about an hour to realize how this insertion sort functioned. I didn’t want to just know the code to write it, I really wanted to understand what was going on behind the code. Adam, being the resourceful teacher that he is, made a diagram with word & index cut-outs and wrote out the code on paper. He moved the cut-outs around through the code to show me what was happening through each iteration of the code. It was brilliant because after an hour of staring at the code and feeling brainwashed, I finally understood! Yay for milestones!
Adam, showing me the logic of an insertion sort with paper cut-outs
But with that understanding came a desire for more goodies! It seemed as though there must be a faster way to sort through data. So we went hunting for information on sorts and we found this really neat animated example of different kinds of sorts:
http://www.inf.ethz.ch/personal/staerk/algorithms/SortAnimation.html
The merge sort really jumped out at me because it seemed super fast and looked neat. I wanted to find the code for a merge sort in ruby and run some test data to see exactly *how much* faster it would be than my hand-made insertion sort!
I quickly found this code:
We ran this code and benchmarked it against my insertion sort method and what we found was… awkward. My naive understanding is that merge arrays are usually much faster than simple insertion arrays. But in this case the merge sort was slower by several magnitudes. Our data was stored in a yaml file and consisted of 500 words alphabetically randomized.
Results:
Insertion Sort:
# Run 100 times
# user system total real
# 0.120000 0.000000 0.120000 ( 0.124449)
# Run 500 times
# user system total real
# 0.470000 0.000000 0.470000 ( 0.477175)
# Run 1000 times
# user system total real
# 0.930000 0.010000 0.940000 ( 0.947101)
Merge Sort:
# Run 100 times
# user system total real
# 0.420000 0.000000 0.420000 ( 0.423855)
# Run 500 times
# user system total real
# 2.040000 0.010000 2.050000 ( 2.066814)
# Run 1000 times
# user system total real
# 4.110000 0.030000 4.140000 ( 4.147465)
WOW, right? Well my guess is that whomever wrote that merge sort method was on crack, or I just don’t understand how it’s supposed to work which is a VERY REAL possibility!
Merge Sorts Average Time: O(n*log(n))
Insertion Sort Average Time: O(n^2)
Clearly, the Merge Sort should have been faster. So my task for tomorrow evening is to find a better example of a ruby merge sort and implement it, benchmark it, and move on with my training. I think Chapter 11 in Pine’s book deals with reading/writing from files and such which should be pretty simple. Tonight was an unusual diversion but was incredibly fun and insightful. I certainly know more about sort methods than I ever thought I would *want* to know! 
Oh, and just for kicks (because I was dying to know) yes, Ruby’s built-in sort method was the fastest on my test data! Made my sorry insertion sort want to cry nails. Ouch.
Ruby Sort:
# Run 100 times
# user system total real
# 0.010000 0.000000 0.010000 ( 0.013807)
# Run 500 times
# user system total real
# 0.070000 0.010000 0.080000 ( 0.066741)
# Run 1000 times
# user system total real
# 0.130000 0.000000 0.130000 ( 0.132825)
