マージソートの実装 - Gobble up pudding

f:id:fa11enprince:20200628235838j:plain
作業記録的なものです。ひどいコードなので、ネットにさらすのもためらわれますが、
とりあえず、マージソートを自力で実装してみました。
誰が書いてもこの程度のアルゴリズムじゃ同じよーな実装になりますね(;'∀')
VC++だと、templateを使ったときにinclusion-modelがどーのこーので
なんもしなきゃテンプレートってcppにかけないんですね……。
VC++じゃなくてもヘッダにすべて書いてしまうのがオヌヌメ方法らしいですね。
マージソートってなによって話ですが
やっぱり僕らの大先生Wikipedia
なかなかわかりやすい解説が書いてあります。

マージソートは、ソートのアルゴリズムで、既に整列してある複数個の列を1個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列も整列されている、というボトムアップの分割統治法による。大きい列を多数の列に分割し、そのそれぞれをマージする作業は並列化できる。
n個のデータを含む配列をソートする場合、最悪計算量O(n log n)である。分割と統合の実装にもよるが、一般に安定なソートを実装できる。インプレースなソートも提案されているが、通常O(n)の外部記憶を必要とする[1]。
（ナイーブな）クイックソートと比べると、最悪計算量は少ない[1]。ランダムなデータでは通常、クイックソートのほうが速い。
マージソート - Wikipedia