[racket] Partion

On Fri, Mar 16, 2012 at 3:49 PM, Jens Axel Søgaard
<jensaxel at soegaard.net> wrote:
> Hi All,
>
> I am looking for a list based algorithm, that solves this problem:
>
> Input:    A list xs of numbers.
> Output: Two lists of numbers ys and zs whose
>             lengths differ at most by one, and:
>
>                for all y in yz and z in zs:    y<=z


Hmmm... Questions: why is a list-based approach a requirement?  Do the
numbers share a special characteristic, such as being densely packed
into a tight range?  If so, bucket sorting could be applied to get
fast O(n) sorting at this stage.