ネタ元 → その差歴然(おまけ)
inplace_merge があんまり知られてなかったみたい。
なので簡単なサンプル、inplace_merge 使ってマージ・ソートを書いてみた。
#include <algorithm>
#include <iterator>
// 単純選択ソート
template<typename Iterator>
void selection_sort(Iterator first, Iterator last) {
// たったこんだけでソートできる。STLらぶ♪
for (; first != last; ++first )
std::iter_swap(first, std::min_element(first,last));
}
// マージ・ソート
template<typename Iterator>
void merge_sort(Iterator first, Iterator last) {
const typename std::iterator_traits<Iterator>::difference_type
threshold = 40; // ウチのマシンだとこのくらいがいっちゃん速い
std::iterator_traits<Iterator>::difference_type
size = std::distance(first,last);
// 要素数が少ないときゃ単純選択ソートに切り替える
if ( size < threshold ) {
selection_sort(first,last);
return;
}
Iterator middle = first; std::advance(middle, size/2); // 中央
merge_sort(first, middle); // 前半[先頭,中央) をソート
merge_sort(middle,last); // 後半[中央,末尾) をソート
std::inplace_merge(first,middle,last); // 前半と後半をマージ
}
// こっからおためし
#include <iostream>
#include <iomanip>
#include <vector>
int main() {
const int N = 50000;
std::vector<int> source(N);
for ( int i = 0; i < N; i++ ) source[i] = i;
std::random_shuffle(source.begin(), source.end());
merge_sort(source.begin(), source.end());
}