ソートされた配列からなるソートされた配列をソート

Question

私は2つのソートされた配列を持っています。 （3,4,5）と（1,3,7,8）と私は組み合わせソート配列（3,4,5,1,3,7,8）を得た。

私は、既にソートされた2つの配列からなるという事実を利用して、すでに結合された配列を分割することなくソートしたいと思います。これを効率的に行う方法はありますか？私はソートされた配列を反復処理し、それに応じて新しい配列に値を入れることによって、これを行う方法について多くのスレッドがあることを知っていますが、このタイプの質問はまだどこでも見ていません。私はCでこれをやりたいのですが、どんなヘルプ/擬似コードも非常に親切に感謝しています。ありがとう！

編集：並べ替えを行う関数は、必要に応じて結合された配列と（おそらく）他の2つの配列の長さだけが与えられます。

Answer 1

元のソート済み配列がすでにある場合は、宛先の記憶域がすでに割り当てられていることを除いて、結合された配列（ではなく、がソートされています）は役立ちません。

ソートされた2つの範囲をマージするアルゴリズムはよく知られていますが、コード化する代わりにstd::mergeを使用することができます。

のみ、非重複入力&出力範囲のために働くことに注意してください：あなたの改正の質問には、あなたの第二の配列から最初の要素に設定し、中央イテレータで、std::inplace_mergeを使用します。

void sort_combined(int *array, size_t total, size_t first) { 
    std::inplace_merge(array, array + first, array + total); 
} 

// and use it like 

int combined[] = {3, 4, 5, 1, 3, 7, 8}; 
const size_t first = 3; 
const size_t second = 4; 
const size_t total = 7; // == sizeof(combined)/sizeof(*combined) 

sort_combined(combined, total, first);