2つの配列が順番に並んでいる場合、どのような場所に並べ替えますか？

Question

I am working on this question。私の関数プロトタイプはrightPosへのI（rightPos-leftPos）/ 2 + leftPosにleftPosを知っている関数の2番目の部分で

static void Sort(byte[] arr, int leftPos, int rightPos) 

であり、（rightPos-leftPos）/ 2を順にソートされています。

私は、どのようにして2つの部品が整っているかを知っている場所でソートを行うことができると考えました。私は何も考えることができませんでした。私はmerge sortのマージ機能を見ましたが、代わりに出力配列を使用しています。

どのようにして、両方のスライスが順番になっていることを知っていますか？

注：私は一時的なメモリとして使用するメイン配列と同じ長さである余分な配列を渡すことができると思っていたが、私はそれぞれのマージ後にArray.Copyを行う必要があると思った方法。

Answer 1

インプレースマージが可能ですが、複雑でパフォーマンスはあまり高くありません。以下は、hereのサンプルコードです。 fromはleftPos、toはrightPos、pivotは(rightPos-leftPos)/2、長さはそれぞれの半分の長さです。

void merge(int from, int pivot, int to, int len1, int len2) { 
    if (len1 == 0 || len2==0) return; 
    if (len1+len2 == 2) { 
    if (compare(pivot, from) < 0) 
    exchange(pivot, from); 
    return; 
    } 
    int first_cut, second_cut; 
    int len11, len22; 
    if (len1 > len2) { 
    len11=len1/2; 
    first_cut = from + len11; 
    second_cut = lower(pivot, to, first_cut); 
    len22 = second_cut - pivot; 
    } else { 
    len22 = len2/2; 
    second_cut = pivot + len22; 
    first_cut = upper(from, pivot, second_cut); 
    len11=first_cut - from; 
    } 
    rotate(first_cut, pivot, second_cut); 
    int new_mid=first_cut+len22; 
    merge(from, first_cut, new_mid, len11, len22); 
    merge(new_mid, second_cut, to, len1 - len11, len2 - len22); 
}