[racket] Partion

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


A simple solution using sort is

     (split-at (sort xs <) (half (length xs))

but using sort must be inefficient.

Another try (that doesn't work):

    (let ([m (median xs)])
        (partition (λ (x) (<= x m)) xs))

To see the bug here,  try   xs = (1 2 2 2 2 2 2).
Since the median in this case is 2, partion will return
two values, one is xs and one is the empty list.

-- 
Jens Axel Søgaard