UPDATED: The code I posted initially had a slight bug in it, this has since been fixed. There is another bug in this code, which is addressed at the end of the post.

This is part two in a continuing (maybe) series about writing Perverse sorting algorithm implementations in Python — part one can be found via this link

After discovering the three-line Quicksort, and showing it to a friend of mine, I was challenged to come up with an implementation of Merge Sort in a similar length of time. I was fairly certain that it couldn’t be done, until I discovered some really nasty features of Python that probably aren’t meant to be exploited in the way that I’ve done so. And so here’s the result (reformatted for line-length issues), followed by a commentary on why this is as damn-awful as I say it is:

def msort2( L ): a,b = ((len( L ) > 1 and (msort2(L[:len( L )/2]), msort2(L[len( L )/2:]))) or (list( L ), [])) return ([(lambda m,n: ((len( n ) == 0 and m.pop( 0 )) or (len( m ) == 0 and n.pop( 0 )) or (m[0] < n[0] and m.pop(0)) or (n.pop(0))))(a,b) for i in xrange(len( a )+len( b ))])

There you have it – merge sort in three lines of Python. Though, in my opinion, it looks a lot more like something a chronic Perl obfuscator would be proud of. So let’s investigate the language “features” that I’ve employed in order to get the code so compact:

The boolean operators

Python’s boolean operators are weird. Instead of returning boolean literals, and and or return one of their operands, in the following way:

A B A and B
True ANYTHING B
False ANYTHING A
A B A or B
True ANYTHING A
False ANYTHING B

It’s easy to convince yourself that this behaviour is correct, if esoteric. Making use of this feature, a and b or c behaves very similarly to C/C++/Java’s ternary operator (enough for our purposes). The fact that these operators are shortcircuited allows us our next abuse (although it prevents the sort from being general – the code can’t quite handle lists with zeroes in them).

list.pop() returns the value it removes

Due to Python not allowing arbitrary assignments as expressions, we need a convenient method of both incrementing a list, and getting the front of that same list at the same time. Happily, pop will return the list element that you pop from the list, which provides us with a value to insert into our comprehended list. C++’s queue template from the STL has both a front() method, as well as a pop() method, probably just to avoid travesties like this (pop does not return a value).

List comprehensions are sequential

For this code to work, it absolutely depends on the list comprehension getting evaluated like a for loop – and thankfully that is the case. If it weren’t, then all of the pop() side-effects would fall apart quite terribly.

lambda

Need I say more?

And there you have it – a strictly non-Pythonic implementation of Merge Sort. Hate mail to the usual address, or if you think you can better it, feel free to comment. Everyone else, take this as an educational exercise in writing readable code.

Small disclaimer: This version is not quite general – it can’t handle lists with zeroes in them: I do have a version which makes use of Python 2.5’s ternary operator, but the code was a lot more readable.