[racket] Partion

From: Danny Yoo (dyoo at cs.wpi.edu)
Date: Fri Mar 16 16:04:43 EDT 2012

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.

Posted on the users mailing list.