Quicksort - the groovy way

I must confess: I didn't write quicksort by myself ever. I always felt it's one of those things that I don't really have to do. Well, Dierk Koenig showed that it might be useful to write your own implementation of quicksort. Not for regular use but for training purposes.

You all know the Collections.sort method, right? We all know it's damn fast, well tested and all that stuff. Let's see what does it take in Groovy to implement quicksort ourselves:

def qs(list) {
  if (list.size() < 2) return list   
  def pivot = list[0]
  def items = list.groupBy { it <=> pivot }.withDefault { [] }
  qs(items[-1]) + items[0] + qs(items[1])
}

WTF? 4 lines plus function definition? And it can easily be shrunk to 3 lines by inlining the pivot variable:

def qs(list) {
  if (list.size() < 2) return list   
  def items = list.groupBy { it <=> list[0] }.withDefault { [] }
  qs(items[-1]) + items[0] + qs(items[1])
}

One of my colleges told me that before he saw the implementation of quicksort in Groovy he didn't quite get the idea, what it does and all. Same here :) I never tried to dig into the details, I just accepted that it works. But with this implementation I just see what's going on! There's nothing to understand, just 3 lines to read :D
By comparison an implementation of bubble sort is around 10 lines long and is about 100 times slower :D
If you're wondering how does this implementation perform by comparison to the Collections.sort() method here are the results (sort a 100 elements list 1000 times):

def qs(list)	Collections.sort()
1938ms	19ms

The actual timing varies but the ratio more/less 100:1 sticks.

It's interesting to note that there's a 10 times difference in timing when invoking list.sort() and Collections.sort(list) in favor for the latter one. That's probably due to the dynamic stuff going on in between.