я надеюсь что это не плагиат, потому что этот алгоритм я придумал сам (из-за того что я сначала не правильно понял оригинальный TreeSort)
эта сортировка обгоняет QuickSort при выриантах значений меньше чем 5000... при 5000 скорости сравниваются
конечно сортировка черпаками быстрее но просто кому нить будет интересно
и так, вот алгоритм (написан на C#)

class sealed Sort
{
    private Sort(){}
    public static void TreeSort(int[] a)
        {
            if (a.Length<2)
                return;
            Node root=new Node(a[0]);
            for(int i=1; i<a.Length; i++)
                AddNode(root,a[i]);
            int k=0;
            ComputeNode(root,a,ref k);
        }
        private static void ComputeNode(Node nd, int[] a, ref int k)
        {
            if (nd.min!=null)
                ComputeNode(nd.min,a,ref k);
            for(int i=0; i<nd.cnt; i++)
                a[k++]=nd.val;
            if(nd.max!=null)
                ComputeNode(nd.max,a,ref k);
        }
        private static void AddNode(Node nd, int value)
        {
            if (nd.val>value)
                if (nd.min==null)
                    nd.min=new Node(value);
                else
                    AddNode(nd.min,value);
            else if (nd.val==value)
                nd.cnt++;
            else
                if (nd.max==null)
                    nd.max=new Node(value);
                else
                    AddNode(nd.max,value);
        }
        class Node
        {
            public int val, cnt=1;
            public Node min, max;
            public Node(int value)
            {
                val=value;
            }
        }

}