1 files changed, 150 insertions, 0 deletions
diff --git a/test/std/algorithms/alg.sorting/alg.sort/stable.sort/stable_sort.pass.cpp b/test/std/algorithms/alg.sorting/alg.sort/stable.sort/stable_sort.pass.cpp
new file mode 100644
index 000000000000..5faa1682135d
--- /dev/null
+++ b/test/std/algorithms/alg.sorting/alg.sort/stable.sort/stable_sort.pass.cpp
@@ -0,0 +1,150 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <algorithm>
+
+// template<RandomAccessIterator Iter>
+//   requires ShuffleIterator<Iter>
+//         && LessThanComparable<Iter::value_type>
+//   void
+//   stable_sort(Iter first, Iter last);
+
+#include <algorithm>
+#include <cassert>
+
+template <class RI>
+void
+test_sort_helper(RI f, RI l)
+{
+    typedef typename std::iterator_traits<RI>::value_type value_type;
+    if (f != l)
+    {
+        long len = l - f;
+        value_type* save(new value_type[len]);
+        do
+        {
+            std::copy(f, l, save);
+            std::stable_sort(save, save+len);
+            assert(std::is_sorted(save, save+len));
+        } while (std::next_permutation(f, l));
+        delete [] save;
+    }
+}
+
+template <class RI>
+void
+test_sort_driver_driver(RI f, RI l, int start, RI real_last)
+{
+    for (RI i = l; i > f + start;)
+    {
+        *--i = start;
+        if (f == i)
+        {
+            test_sort_helper(f, real_last);
+        }
+    if (start > 0)
+        test_sort_driver_driver(f, i, start-1, real_last);
+    }
+}
+
+template <class RI>
+void
+test_sort_driver(RI f, RI l, int start)
+{
+    test_sort_driver_driver(f, l, start, l);
+}
+
+template <unsigned sa>
+void
+test_sort_()
+{
+    int ia[sa];
+    for (int i = 0; i < sa; ++i)
+    {
+        test_sort_driver(ia, ia+sa, i);
+    }
+}
+
+void
+test_larger_sorts(unsigned N, unsigned M)
+{
+    assert(N != 0);
+    assert(M != 0);
+    // create array length N filled with M different numbers
+    int* array = new int[N];
+    int x = 0;
+    for (int i = 0; i < N; ++i)
+    {
+        array[i] = x;
+        if (++x == M)
+            x = 0;
+    }
+    // test saw tooth pattern
+    std::stable_sort(array, array+N);
+    assert(std::is_sorted(array, array+N));
+    // test random pattern
+    std::random_shuffle(array, array+N);
+    std::stable_sort(array, array+N);
+    assert(std::is_sorted(array, array+N));
+    // test sorted pattern
+    std::stable_sort(array, array+N);
+    assert(std::is_sorted(array, array+N));
+    // test reverse sorted pattern
+    std::reverse(array, array+N);
+    std::stable_sort(array, array+N);
+    assert(std::is_sorted(array, array+N));
+    // test swap ranges 2 pattern
+    std::swap_ranges(array, array+N/2, array+N/2);
+    std::stable_sort(array, array+N);
+    assert(std::is_sorted(array, array+N));
+    // test reverse swap ranges 2 pattern
+    std::reverse(array, array+N);
+    std::swap_ranges(array, array+N/2, array+N/2);
+    std::stable_sort(array, array+N);
+    assert(std::is_sorted(array, array+N));
+    delete [] array;
+}
+
+void
+test_larger_sorts(unsigned N)
+{
+    test_larger_sorts(N, 1);
+    test_larger_sorts(N, 2);
+    test_larger_sorts(N, 3);
+    test_larger_sorts(N, N/2-1);
+    test_larger_sorts(N, N/2);
+    test_larger_sorts(N, N/2+1);
+    test_larger_sorts(N, N-2);
+    test_larger_sorts(N, N-1);
+    test_larger_sorts(N, N);
+}
+
+int main()
+{
+    // test null range
+    int d = 0;
+    std::stable_sort(&d, &d);
+    // exhaustively test all possibilities up to length 8
+    test_sort_<1>();
+    test_sort_<2>();
+    test_sort_<3>();
+    test_sort_<4>();
+    test_sort_<5>();
+    test_sort_<6>();
+    test_sort_<7>();
+    test_sort_<8>();
+
+    test_larger_sorts(256);
+    test_larger_sorts(257);
+    test_larger_sorts(499);
+    test_larger_sorts(500);
+    test_larger_sorts(997);
+    test_larger_sorts(1000);
+    test_larger_sorts(1009);
+}