Why aren't we all speaking LISP now?

[Danyel Fisher]

> You can always write an insertion sort and get it right. You can always
> write a bubble sort and get it right. The code is very similar in length.
> Conceptually, an insertion sort is more logical (despite this, *everyone*
> I've known, including myself, wrote a bubble sort as their first ever
sort -
> I wonder why?).

In my case, because after we wrote the algorithm, we stood up in the
classroom and buble sorted ourselves by age. It was very easy to simply
match pairs.

Also, it works as a naive recursive definition of sort in a world of lists:
   A list is sorted if the elements one and two are in the correct
   order, and elements numbered 2 through n are sorted.

An intuitive "fix"--which implements the bubble sort--is:
def sort(list):
  if list[0] < list[1]:
    return list[0] + sort( list[1:] )
 else:
   list[0], list[1] = list[1],list[0]
   return sort( list[0]+sort(list[1:]))

And, yes, that double recursive call in the second half is necessary, and it
pretty much makes it clear WHY bubble sort isn't as cool as other sorts.
Admittedly, this doesn't have ANY optimizations, and it rather should. Any
ideas of how to fix?

Danyel