回答（途中） with Concurrent Clean

[id:lethevert:20070124:p2]
配列を、何らかの方法でソートしてから比較すれば・・・と思ったけれど、ある程度かいてから、その何らかというものが容易でないということに気づいてそのアプローチを断念。
とりあえず、書きかけのコード。

module Main

import StdInt, StdArray, StdOverloaded, StdClass, StdEnum
     , OptBase

swap i j arr
    | i==j = arr
           = swap arr
  where
    swap arr=:{[i]=ai,[j]=aj}
        # (l,arr) = usize arr
        = swap_edge (dec l) {arr & [i]=aj,[j]=ai}

    swap_edge -1 arr = arr
    swap_edge k arr=:{[k]=ak} | ak == i = swap_edge (dec k) {arr & [k]=j}
                              | ak == j = swap_edge (dec k) {arr & [k]=i}
                                        = swap_edge (dec k) arr

sort_first arr = case find_root 0 arr of
                   (i,arr) = swap 0 i arr
  where
    find_root k arr=:{[k]=ak} | k == ak = (k,arr)
                                        = find_root ak arr

sort_rest l p i arr | i>=l = arr
                    # (i,arr) = find_child i i arr
                    = sort_rest l (inc p) i arr
  where
    find_child i k arr | k>=l  = (i,arr)
                       # (ak,arr) = arr![k]
                       | p==ak # arr = swap i k arr
                               = find_child (inc i) (inc k) arr
                               = find_child i (inc k) arr

sort arr # (l,arr) = usize arr
         = arr |> sort_first
               |> sort_rest l 0 1

/* test */
Start = sort tree

tree :: *{#Int}
tree = {1,1,9,4,9,6,9,9,0,0}