私の教授は私のクラスに、3 部分割とマージを使用して配列にマージソートを実装するように割り当てました。
それが教授からの正確な質問でした。問題は、3 方向のマージソートのようなものを見つけられなかったことです。3 方向のクイックソートしか知らないので、彼はおそらく配列を取り、それを 3 つの部分に分割し、それらの 3 つの部分を一緒にマージソートするつもりだったと思いました。最初の 2 つの部分を一緒にマージソートしてから、結合した部分を 3 番目の部分とマージソートすることでこれを行います。
私は正しく考え、正しいことをしましたか（すでに実装されていますが、私の質問とは関係がないため、コードを投稿していません）、または間違っていることを理解していて、3方向マージソートのようなものがありますか私が気づいていないこと。
教授は、私たちがまだ学んでいないことに関する課題を私たちに与える傾向があるので、私はこれについて非常に懐疑的であり、グーグルなどでできる限り調べました.
Once you mergesorted the three sub arrays, you can merge them together in one go: compare the first elements of all three and place the smallest into the combined array, then take the next element from the array you took the smallest from and do the compariosn again until all subarray elements are accounted for.
Make sure you hande the case where there are only two elements in the array (so you cannot partition it into three non-empty parts). Also, in the above paragraph, one array will be empty before the others when merging, so you need to account for that too.
これは、3 部構成のマージ ソートと呼ばれます。http://mathbits.com/MathBits/CompSci/Arrays/Merge.htmをご覧ください。