背景

2014年11月にc++で安定ソートを実装しました.

学校の課題で何らかの成績の順位付けをする必要がありました. 秒数が同じ時はインデックスが小さいほうが順位が高いという指定があったため安定ソートを使う必要がありました. 別に課題の指定では自前でソート関数を実装する必要はありませんでしたが, constexpr対応させたかったのでマージソートを自前で実装しました. 本当に対応してるかは知りません.

インターフェイスはできるだけstd::stable_sortに準じているようです.

当時の私(大学1年)はヒマそうで羨ましい. この時期に課題を適当に終わらせてなにか実用的なものを作ってれば… やめておこう, 過去を悔やんでも仕方がない.

ソースコード

reinvention

stdと名前空間を分けるためにreinvention名前空間内に定義.

reinvention of the wheel → 車輪の再発明.

merge

マージする関数.

help_stable_sort

要素数が2以下になるまで再帰してmerge.

main

課題本体を解く.

こんな適当な記述なのに比較関数にラムダ式使えてネイティブコンパイルできるc++14は素敵な言語だなあって当時の私は思ってました. いや今も思ってますけど.

クイックソート

クイックソートも実装したかったから実装していた. 本当に暇だったんだな…

比較関数を高階にするのは飽きたらしい.

性能

当然標準c++ライブラリの実装よりおおよそ1.5倍程度遅かった. 多分真面目に高速化するならメモリ効率なども気にする必要があるのだろう. 標準の実装を読もうと思ったがプリプロセッサで目が潰れた.