Merge Sort
There are certain incidents in your life that stick around in your brain for a long time. One such incident for me was a job interview a few years ago (at an unnamed company) where I crashed and burned quite spectacularly in the space of 2 hours. It was so bad that mid way through the first interview, I no longer even wanted the job, I just wanted to cut my losses and go back home. Needless to say, the post-mortem analysis of that incident has been going on for a few years. Over the years, the incident has lost a lot of the emotional rawness. To me, it has turned into an analysis of how programming languages shape the way you think about solving problems.
On the day of the interview, I was functioning on an hour’s sleep from the previous night, it did not help at all when the first question I was asked was to write the Merge Sort algorithm on a whiteboard. Not a very difficult question. The classic divide and conquer algorithm I said aloud, break the unsorted list into smaller lists, sort the smaller lists and merge them back together. The devil as always is in the details. In this case, it was in the details of how I translated that sentence in English into code on a whiteboard. No IDE to tell you how badly the syntax is screwed up. No REPL environments to test out a few things. No writing the unit test first and going back and refining the algorithm over successive attempts. A whiteboard is the most stark programming environment in the world, especially when the code you write is supposed to meet some standards of rigor.
As always, I was granted the luxury of writing the algorithm in any programming language. Over the years, in analyzing the incident, I have realized that this choice is not a luxury. In fact, the worst thing you can do is pick the wrong programming language to think in. Even simple things like the representation and manipulation of a list get in the way of how you solve the problem. The language, the libraries, the idioms commonly used, all shape the way you approach any problem.
From that point, any new language I try out has to go through my Merge Sort test. I had no clear favorite, until I tried it in Erlang. It was a like a walk in the park with Erlang (I admit I did compile and run it a couple of times, but in my defense I am still learning Erlang and had syntax errors). Here is the merge routine I came up with on the first attempt.
merge(L1, []) -> L1;
merge([], L2) -> L2;
merge([H1|R1], [H2|R2]) when H1 =< H2 -> [H1] ++ merge(R1, [H2] ++ R2);
merge([H1|R1], [H2|R2]) when H1 > H2 -> [H2] ++ merge([H1] ++ R1, R2).
Pattern matching, recursion and literal syntax to deal with lists just seem to lend themselves to these kinds of problems.
Den ganzen Beitrag lesen…