What can I say, combsorts are cool. It's like a bubble sort except with the concept of a gap added in. The gap makes up for the bubble sort's inefficiency quite well by allowing the sort to make rough passes first.
The crazy man responsible for getting me interested in the combsort is Wayne Conrad, and there's a whole pile of additional information on his combsort site.
Aside from the spiffy technical aspects of the combsort, I primarily like it because it's a good excuse to go learn new languages which happens to be one of my favorite hobbies. What I have found with the combsort is that it has intriguing differences in the way it looks and acts in different languages. For example, the Lisp combsort was truly exciting as I discovered that the gap and swapped variables became useless baggage in that language.
It all started one day when Wayne mentioned that he did not have a Perl combsort yet, so I offered to help him out on the condition that he also posted an obfuscated perl version. Assuming you've seen Wayne's site, you'll notice that the perl version is nearly the same as the Ruby version except with a lot of dollar signs and semi-colons.
The fun begins with the obfuscated version. To make this version I took the original Perl version, cleaned it up a little, and then incrementally started changing it. First the variables disappeared, then the subroutines became anonymous, and finally I made creative use of continuation blocks to turn the whole thing into a single line of code (that's right, not multiple lines all smashed together). I also decided that the whole counting thing done in the inner loop was too obvious, so it uses bit shifting and logarithms to do the same thing. I think it turned out fairly well, especially since the TidyPerl program doesn't understand it, and just turns it into a bigger mess. (-=
Next I decided to do combsort in Shakespeare. Yes, a group of college students actually did make a Shakespeare Language. All I can say is that it seemed like a good idea at the time, and I regret nothing. (-=
This was by far the most difficult combsort to write, and especially debug. It took 2 weeks of my spare time, but I finally got it work while at RubyConf. It turned out to be quite the Shakespearian play at 466 lines. In it, I even managed to emulate function calls and arrays in a language that does not support those two constructs.
I've been wanting to learn Lisp for a while now, and would you believe Wayne didn't have a combsort in Lisp yet? Naturally I was forced against my will to proceed. (-=
I must say, the Lisp combsort is my favorite so far. It's different from the other combsorts in the the gap and swapped variables are completely useless in Lisp. They are present in the procedural languages because we modify the array in place, and thus data is lost along the way. In Lisp, we see how tail recursion is our friend, and how very small functions can be easily assembled to perform complex tasks. Every coder knows that it's a good idea to chop things up into small pieces, but once you start doing functional programming it becomes crystal clear not only what the benefits are, but also some great ways to do it. I found while writing this combsort that when doing functional programming, the language will tell you how to split things up, so just go with it and it'll work out fine. For example, the outer loop in the combsort seems simple enough, but in Lisp, the language indicated that it was really two functions that were mutually recursive, and after I finally stopped resisting and did it, the code rolled out beautifully from there.
Ok, there's been a lot of talk about a Haskell version of combsort, and since I already have a lisp version done in functional style, I figured the Haskell version would be simple. As it turns out, I was right. Haskell is a pretty cool language, it looks nearly identical to the lisp version I did, but that's probably because I'm not a super Haskell coder yet (consider this to be my "hello world" program.) I/O is a bit interesting in Haskell, it pretends to be functional, and from a user standpoint it mostly is. The syntax is a bit pickier than I would like in a language, but I'm sure it makes sense once you get a decoder ring. (-= I think there's some refactoring to be done to be more in line with the spirit of the language, but this will do for now.
So we have plenty of combsorts in plenty of languages, but they all run on normal computers. What fun is that? None. So that's why I went off and wrote combsort in Postscript. Ok, that's not the only reason why, I'm also crazy, but you should have figured that part out on your own by now. So here it is, combsort in Postscript; now go forth and make your printer sort things...
So it's been several years since I've added a combsort, but it was about time to do a combsort in BrainFuck. If you're not familiar with the language, it has just a handful of opcodes, and certainly no convenience features. I didn't write this directly in BrainFuck, I used a tool called BrainFix to translate a slightly less insane syntax to the more insane syntax. Interestingly enough, this does not function properly in the BrainFuck interpreters I've tried; however, it runs perfectly through bf2c and then compiles nicely via gcc.