From: Michael Judge <mjudge@...>
Date: 2006-02-07T17:28:21+09:00
Subject: Feeling sharp?  Sort an array subset in place.

Here's the situation: I have an array and I'd like to sort certain
elements in place -- without touching the others.

Unsorted array contents:
  3 <-- sort me!
  x
  1 <-- sort me!
  y
  2 <-- sort me!

Sorted array contents
  1
  x
  2
  y
  3

See how 1, 2, and 3 played musical chairs?  That's exactly what we
want. It seems like there should be an easy one, two or three-line way
to do this given an array and a test condition (for identifying
elements which need sorting.)

How would you do it?

(My solution was a dirty cheat, it involved building a hash of {from =>
to} moves, cloning the original array contents, then changing each
element one at a time. Blah.  There's got to be a sexier way.)