C++のsortとstable_sortの違い

#概要
sortには同位の場合に、その順番を保障する安定したソートと保障していない安定しないソートの二種類がある。

STLで提供されているsortは安定しないソートで、stable_sortは安定しているソートである。

sortで安定したソートを実現したい場合は、比較用の関数で同位だったら、元の並び順で比較してやれば安定する。

##検証コード

```cpp

#include <iostream>  // cout, endl
#include <algorithm> // stable_sort, for_each
#include <vector>
#include <time.h>     // for clock()
#include <string>

using namespace std;
struct test
{
	int order;
	int key;
};

bool CustPredicate(test elem1, test elem2)
{
	if (elem1.key > elem2.key)
		return false;

	if (elem1.key < elem2.key)
		return true;
	return false; // trueにするとDebugでAssert。同値の場合、順序が逆になる
	// https://support.microsoft.com/en-us/kb/949171
}

bool CustPredicate2(test elem1, test elem2)
{
	if (elem1.key > elem2.key)
		return false;

	if (elem1.key < elem2.key)
		return true;
	// 同じ場合は元の並び順で決める
	return elem1.order < elem2.order;
}

vector<test> createList(size_t sz)
{
	std::vector<test> list;
	// データ数が少ないと、安定してないソートでも安定しているように見えるので注意
	for (size_t i = 0; i < sz; ++i){
		test t;
		t.order = i;
		t.key = i % 3;
		list.push_back(t);
	}
	return list;
}


int main() {
	{
		vector<test> list = createList(32);
		cout << "\n不安定なソート 32件-----------------------------------\n";
		sort(list.begin(), list.end(), &CustPredicate);
		for (size_t i = 0; i < list.size(); ++i){
			cout << "(" << list[i].key << ":" << list[i].order << ")";
		}
	}
	{
		vector<test> list = createList(33);
		cout << "\n不安定なソート 33件-----------------------------------\n";
		sort(list.begin(), list.end(), &CustPredicate);
		for (size_t i = 0; i < list.size(); ++i){
			cout << "(" << list[i].key << ":" << list[i].order << ")";
		}
	}
	{
		vector<test> list = createList(32);
		cout << "\n安定なソート 33件-----------------------------------\n";
		stable_sort(list.begin(), list.end(), &CustPredicate);
		for (size_t i = 0; i < list.size(); ++i){
			cout << "(" << list[i].key << ":" << list[i].order << ")";
		}
	}
	{
		vector<test> list = createList(33);
		cout << "\n安定なソート 33件-----------------------------------\n";
		stable_sort(list.begin(), list.end(), &CustPredicate);
		for (size_t i = 0; i < list.size(); ++i){
			cout << "(" << list[i].key << ":" << list[i].order << ")";
		}
	}
	{
		vector<test> list = createList(33);
		cout << "\n不安定なソートを比較関数でなんとかする 33件-----------------------------------\n";
		stable_sort(list.begin(), list.end(), &CustPredicate2);
		for (size_t i = 0; i < list.size(); ++i){
			cout << "(" << list[i].key << ":" << list[i].order << ")";
		}
	}
	size_t sort_size = 500000;
	{
		vector<test> list = createList(sort_size);
		cout << "\n不安定ソートの速度-----------------------------------\n";
		clock_t start = clock();    // スタート時間
		sort(list.begin(), list.end(), &CustPredicate2);
		clock_t end = clock();     // 終了時間
		std::cout << "\nduration = " << (double)(end - start) / CLOCKS_PER_SEC << "sec.\n";
	}
	{
		vector<test> list = createList(sort_size);
		cout << "\n安定ソートの速度-----------------------------------\n";
		clock_t start = clock();    // スタート時間
		stable_sort(list.begin(), list.end(), &CustPredicate2);
		clock_t end = clock();     // 終了時間
		std::cout << "\nduration = " << (double)(end - start) / CLOCKS_PER_SEC << "sec.\n";
	}
	{
		vector<test> list = createList(sort_size);
		cout << "\n比較関数で安定させるソート-----------------------------------\n";
		clock_t start = clock();    // スタート時間
		sort(list.begin(), list.end(), &CustPredicate2);
		clock_t end = clock();     // 終了時間
		std::cout << "\nduration = " << (double)(end - start) / CLOCKS_PER_SEC << "sec.\n";
	}
	cout << endl << endl;


}

```

##結果
###VS2013 + Windows7

```

不安定なソート 32件-----------------------------------
(0:0)(0:3)(0:6)(0:9)(0:12)(0:15)(0:18)(0:21)(0:24)(0:27)(0:30)
(1:1)(1:4)(1:7)(1:10)(1:13)(1:16)(1:19)(1:22)(1:25)(1:28)(1:31)
(2:2)(2:5)(2:8)(2:11)(2:14)(2:17)(2:20)(2:23)(2:26)(2:29)
不安定なソート 33件-----------------------------------
(0:0)(0:21)(0:30)(0:3)(0:12)(0:27)(0:6)(0:15)(0:24)(0:9)(0:18)
(1:1)(1:4)(1:7)(1:10)(1:13)(1:16)(1:19)(1:22)(1:25)(1:28)(1:31)
(2:14)(2:23)(2:8)(2:17)(2:26)(2:5)(2:20)(2:29)(2:2)(2:11)(2:32)
安定なソート 33件-----------------------------------
(0:0)(0:3)(0:6)(0:9)(0:12)(0:15)(0:18)(0:21)(0:24)(0:27)(0:30)
(1:1)(1:4)(1:7)(1:10)(1:13)(1:16)(1:19)(1:22)(1:25)(1:28)(1:31)
(2:2)(2:5)(2:8)(2:11)(2:14)(2:17)(2:20)(2:23)(2:26)(2:29)
安定なソート 33件-----------------------------------
(0:0)(0:3)(0:6)(0:9)(0:12)(0:15)(0:18)(0:21)(0:24)(0:27)(0:30)
(1:1)(1:4)(1:7)(1:10)(1:13)(1:16)(1:19)(1:22)(1:25)(1:28)(1:31)
(2:2)(2:5)(2:8)(2:11)(2:14)(2:17)(2:20)(2:23)(2:26)(2:29)(2:32)
不安定なソートを比較関数でなんとかする 33件-----------------------------------
(0:0)(0:3)(0:6)(0:9)(0:12)(0:15)(0:18)(0:21)(0:24)(0:27)(0:30)
(1:1)(1:4)(1:7)(1:10)(1:13)(1:16)(1:19)(1:22)(1:25)(1:28)(1:31)
(2:2)(2:5)(2:8)(2:11)(2:14)(2:17)(2:20)(2:23)(2:26)(2:29)(2:32)
不安定ソートの速度-----------------------------------

duration = 0.12sec.

安定ソートの速度-----------------------------------

duration = 0.081sec.

比較関数で安定させるソート-----------------------------------

duration = 0.109sec.

```

VisualStudioのC++だとsort関数は32件までは挿入ソートをしているので安定している。
それいこうは、クイックソート。
stable_sortも32件までは挿入ソートで、それ以降はマージソート
速度的には、stable_sortの方が早い。そのかわり、マージソートなのでメモリを消費している。

####stable_sortでassertが出る場合
vs2005以降でstable_sortを使うとAssertがでる場合がある。
これは同値の場合にtrueを返してしまっているため。
https://support.microsoft.com/en-us/kb/949171

trueを返すと同位の場合、逆順にならんでしまう。

###Debian7 + g++ 4.7.4

```
不安定なソート 32件-----------------------------------
(0:24)(0:0)(0:15)(0:18)(0:12)(0:21)(0:9)(0:6)(0:27)(0:3)(0:30)
(1:25)(1:16)(1:22)(1:28)(1:19)(1:31)(1:13)(1:10)(1:7)(1:4)(1:1)
(2:17)(2:14)(2:20)(2:11)(2:23)(2:8)(2:26)(2:5)(2:29)(2:2)
不安定なソート 33件-----------------------------------
(0:0)(0:18)(0:15)(0:21)(0:12)(0:24)(0:9)(0:27)(0:6)(0:30)(0:3)
(1:25)(1:28)(1:22)(1:19)(1:31)(1:1)(1:16)(1:13)(1:10)(1:7)(1:4)
(2:17)(2:14)(2:20)(2:11)(2:23)(2:8)(2:26)(2:5)(2:29)(2:2)(2:32)
安定なソート 33件-----------------------------------
(0:0)(0:3)(0:6)(0:9)(0:12)(0:15)(0:18)(0:21)(0:24)(0:27)(0:30)
(1:1)(1:4)(1:7)(1:10)(1:13)(1:16)(1:19)(1:22)(1:25)(1:28)(1:31)
(2:2)(2:5)(2:8)(2:11)(2:14)(2:17)(2:20)(2:23)(2:26)(2:29)
安定なソート 33件-----------------------------------
(0:0)(0:3)(0:6)(0:9)(0:12)(0:15)(0:18)(0:21)(0:24)(0:27)(0:30)
(1:1)(1:4)(1:7)(1:10)(1:13)(1:16)(1:19)(1:22)(1:25)(1:28)(1:31)
(2:2)(2:5)(2:8)(2:11)(2:14)(2:17)(2:20)(2:23)(2:26)(2:29)(2:32)
不安定なソートを比較関数でなんとかする 33件-----------------------------------
(0:0)(0:3)(0:6)(0:9)(0:12)(0:15)(0:18)(0:21)(0:24)(0:27)(0:30)
(1:1)(1:4)(1:7)(1:10)(1:13)(1:16)(1:19)(1:22)(1:25)(1:28)(1:31)
(2:2)(2:5)(2:8)(2:11)(2:14)(2:17)(2:20)(2:23)(2:26)(2:29)(2:32)
不安定ソートの速度-----------------------------------

duration = 0.256623sec.

安定ソートの速度-----------------------------------

duration = 0.253698sec.

比較関数で安定させるソート-----------------------------------

duration = 0.252346sec.
```

g++の場合、件数が32件でも不安定になっているので、おそらく、件数によるアルゴリズムの切り替えはしてないくさい。（あるいはもっと件数が小さい）

そして、stable_sortとsortの速度差がVisualStudioC++より小さい。

おそらく、処理系によって実装の方法が違っているっぽい。