計数ソートを入力順にソートした際の安定性


下の疑似コードで実装された計数ソート(Counting
Sort)の探索を現在と逆順にした場合、安定したソートを保持したままにするにはどの方法が効率がいいでしょうか？  
事実、このアルゴリズムでは入力配列を後ろからソートしないと、同じ要素が現れた場合その要素の順番は逆になってしまい、安定したソートではなくなります。  
私は。同じ要素が複数回出現した場合に限り、その要素数-1をしたものをそれぞれのカウンターから引けばいいと思ったのですが、その場合はもう一つ余計な配列を用意しなければならず、非効率的ではないかと指摘されました。しかし、それ以外の方法が思いつきません。  
なにか手法などありましたら教えていただけると幸いです。

pseudo-code (reference: Algorithm Introduction, MIT Press)

[code]

    COUNTING-SORT(A,B,k) 
    C[0..k] を新しい配列とする 
    for i = 0 to k 
        C[i] = 0 
    for j = 1 to A.length 
        C[A[j]] = C[A[j]] + 1 
        //C[i] は i と等しい要素の数を示す． 
    for i = 1 to k 
        C[i] = C[i] + C[i−1] 
        //C[i] は i 以下の要素の数を示す． 
    for j = A.length downto 1 
        B[C[A[j]]] = A[j]
        C[A[j]] = C[A[j]]−1
    
[/code]

このアルゴリズムの最後のforループを、for (j = 1 to A.length) にしたいです




このアルゴリズムでは最後のループが回る直前の `C[i]` の値が、配列 `B` における値 `i` の **末尾**
のインデックスを示すように計算されています。このため最後のループでは配列 `A` を **後ろ** から走査する形が自然です。

逆に考えると、最後のループで配列 `A` を **前** から走査したければ、`C[i]` の値が配列 `B` における値 `i` の **先頭**
のインデックスを示すように計算すれば良いです。

これを計算するやり方はいくつかあると思いますが、たとえば以下のようにできます。

[code]

    COUNTING-SORT(A, B, k)
    C[0..(k + 1)] を新しい配列とする
    for i = 0 to (k + 1)
        C[i] = 0
    for j = 1 to A.length
        C[A[j] + 1] = C[A[j] + 1] + 1
        //C[i + 1] は i と等しい要素の数を示す．
    for i = 1 to k
        C[i] = C[i] + C[i−1]
        //C[i] は i 未満の要素の数を示す (i ∈ {1..k})．
    for j = 1 to A.length
        C[A[j]] = C[A[j]] + 1
        B[C[A[j]]] = A[j]
    
[/code]




このアルゴリズムでは最後のループが回る直前の `C[i]` の値が、配列 `B` における値 `i` の **末尾**
のインデックスを示すように計算されています。このため最後のループでは配列 `A` を **後ろ** から走査する形が自然です。

逆に考えると、最後のループで配列 `A` を **前** から走査したければ、`C[i]` の値が配列 `B` における値 `i` の **先頭**
のインデックスを示すように計算すれば良いです。

これを計算するやり方はいくつかあると思いますが、たとえば以下のようにできます。

[code]

    COUNTING-SORT(A, B, k)
    C[0..(k + 1)] を新しい配列とする
    for i = 0 to (k + 1)
        C[i] = 0
    for j = 1 to A.length
        C[A[j] + 1] = C[A[j] + 1] + 1
        //C[i + 1] は i と等しい要素の数を示す．
    for i = 1 to k
        C[i] = C[i] + C[i−1]
        //C[i] は i 未満の要素の数を示す (i ∈ {1..k})．
    for j = 1 to A.length
        C[A[j]] = C[A[j]] + 1
        B[C[A[j]]] = A[j]
    
[/code]

