Index: include/bits/stl_algo.h
===================================================================
--- include/bits/stl_algo.h	(revision 203853)
+++ include/bits/stl_algo.h	(working copy)
@@ -1917,7 +1917,7 @@
 				_RandomAccessIterator __last, _Compare __comp)
     {
       _RandomAccessIterator __mid = __first + (__last - __first) / 2;
-      std::__move_median_to_first(__first, __first + 1, __mid, (__last - 2),
+      std::__move_median_to_first(__first, __first + 1, __mid, (__last - 1),
 				  __comp);
       return std::__unguarded_partition(__first + 1, __last, __first, __comp);
     }
Index: testsuite/25_algorithms/nth_element/58800.cc
===================================================================
--- testsuite/25_algorithms/nth_element/58800.cc	(revision 0)
+++ testsuite/25_algorithms/nth_element/58800.cc	(working copy)
@@ -0,0 +1,47 @@
+// Copyright (C) 2005-2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// 25.3.2 [lib.alg.nth.element]
+
+// { dg-options "-std=gnu++0x" }
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::random_access_iterator_wrapper;
+
+typedef test_container<int, random_access_iterator_wrapper> Container;
+
+int main()
+{
+        std::vector<int> v = {
+                207089,
+                202585,
+                180067,
+                157549,
+                211592,
+                216096,
+                207089
+        };
+
+        Container con(v.data(), v.data() + 7);
+
+        std::nth_element(con.begin(), con.begin() + 3, con.end());
+        return 0;
+}
Index: testsuite/25_algorithms/nth_element/random_test.cc
===================================================================
--- testsuite/25_algorithms/nth_element/random_test.cc	(revision 0)
+++ testsuite/25_algorithms/nth_element/random_test.cc	(working copy)
@@ -0,0 +1,65 @@
+// Copyright (C) 2005-2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++0x" }
+// { dg-options "-std=gnu++0x -DSIMULATOR_TEST" { target simulator } }
+
+// 25.4.2 [lib.alg.nth.element]
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+#include <random>
+#include <testsuite_containergen.h>
+
+
+using __gnu_test::test_container;
+using __gnu_test::random_access_iterator_wrapper;
+
+typedef test_container<int, random_access_iterator_wrapper> Container;
+
+bool test __attribute__((unused)) = true;
+
+struct testNthElement
+{
+  template<typename Container, typename RandomGen>
+  void operator()(Container con, RandomGen& rg)
+  {
+    int size = con.end() - con.begin();
+    int element = rg() % (size + 1);
+
+    std::nth_element(con.begin(), con.begin() + element, con.end());
+
+    if(element < size)
+      {
+        for(int i = 0; i < element; ++i)
+          {
+            VERIFY(con.val(i) <= con.val(element));
+          }
+        for(int i = element + 1; i < size; ++i)
+          {
+            VERIFY(con.val(i) >= con.val(element));
+          }
+      }
+  }
+};
+
+int 
+main()
+{
+  __gnu_test::test_containers<Container>(testNthElement());
+}
Index: testsuite/25_algorithms/partial_sort/random_test.cc
===================================================================
--- testsuite/25_algorithms/partial_sort/random_test.cc	(revision 0)
+++ testsuite/25_algorithms/partial_sort/random_test.cc	(working copy)
@@ -0,0 +1,63 @@
+// Copyright (C) 2005-2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++0x" }
+// { dg-options "-std=gnu++0x -DSIMULATOR_TEST" { target simulator } }
+
+// 25.4.1.3 [lib.alg.partial.sort]
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+#include <random>
+#include <testsuite_containergen.h>
+
+
+using __gnu_test::test_container;
+using __gnu_test::random_access_iterator_wrapper;
+
+typedef test_container<int, random_access_iterator_wrapper> Container;
+
+bool test __attribute__((unused)) = true;
+
+struct testPartialSort
+{
+  template<typename Container, typename RandomGen>
+  void operator()(Container con, RandomGen& rg)
+  {
+    int size = con.end() - con.begin();
+    int element = rg() % (size + 1);
+
+    std::partial_sort(con.begin(), con.begin() + element, con.end());
+
+    VERIFY(std::is_sorted(con.begin(), con.begin() + element));
+    
+    if(element > 0)
+      {
+        for(int i = element; i < size; ++i)
+          {
+            VERIFY(con.val(element - 1) <= con.val(i));
+          }
+      }
+  }
+};
+
+int 
+main()
+{
+  __gnu_test::test_containers<Container>(testPartialSort());
+}
Index: testsuite/25_algorithms/partial_sort_copy/random_test.cc
===================================================================
--- testsuite/25_algorithms/partial_sort_copy/random_test.cc	(revision 0)
+++ testsuite/25_algorithms/partial_sort_copy/random_test.cc	(working copy)
@@ -0,0 +1,66 @@
+// Copyright (C) 2005-2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++0x" }
+// { dg-options "-std=gnu++0x -DSIMULATOR_TEST" { target simulator } }
+
+// 25.4.1.4 [lib.alg.partial.sort.copy]
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+#include <random>
+#include <testsuite_containergen.h>
+#include <vector>
+
+using __gnu_test::test_container;
+using __gnu_test::random_access_iterator_wrapper;
+
+typedef test_container<int, random_access_iterator_wrapper> Container;
+
+bool test __attribute__((unused)) = true;
+
+struct testPartialSortCopy
+{
+  template<typename Container, typename RandomGen>
+  void operator()(Container con, RandomGen& rg)
+  {
+    int size = con.end() - con.begin();
+    int element = rg() % (size + 1);
+
+    std::vector<int> outvec(element + 1); // add +1 to stop empty issues
+
+    Container out(outvec.data(), outvec.data() + element);
+
+    std::partial_sort_copy(con.begin(), con.end(), out.begin(), out.begin() + element);
+
+    VERIFY(std::is_sorted(out.begin(), out.begin() + element));
+
+    std::sort(con.begin(), con.end());
+    
+    for(int i = 0; i < element; ++i)
+      {
+	VERIFY(con.val(i) == out.val(i));
+      }
+  }
+};
+
+int 
+main()
+{
+  __gnu_test::test_containers<Container>(testPartialSortCopy());
+}
Index: testsuite/25_algorithms/sort/random_test.cc
===================================================================
--- testsuite/25_algorithms/sort/random_test.cc	(revision 0)
+++ testsuite/25_algorithms/sort/random_test.cc	(working copy)
@@ -0,0 +1,51 @@
+// Copyright (C) 2005-2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++0x" }
+// { dg-options "-std=gnu++0x -DSIMULATOR_TEST" { target simulator } }
+
+// 25.4.1 [lib.alg.sort]
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+#include <random>
+#include <testsuite_containergen.h>
+
+
+using __gnu_test::test_container;
+using __gnu_test::random_access_iterator_wrapper;
+
+typedef test_container<int, random_access_iterator_wrapper> Container;
+
+bool test __attribute__((unused)) = true;
+
+struct testSort
+{
+  template<typename Container, typename RandomGen>
+  void operator()(Container con, RandomGen& rg)
+  {
+    std::sort(con.begin(), con.end());
+    VERIFY(is_sorted(con.begin(), con.end()));
+  }
+};
+
+int 
+main()
+{
+  __gnu_test::test_containers<Container>(testSort());
+}
Index: testsuite/util/testsuite_containergen.h
===================================================================
--- testsuite/util/testsuite_containergen.h	(revision 0)
+++ testsuite/util/testsuite_containergen.h	(working copy)
@@ -0,0 +1,110 @@
+// -*- C++ -*-
+
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the terms
+// of the GNU General Public License as published by the Free Software
+// Foundation; either version 3, or (at your option) any later
+// version.
+
+// This library is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+// General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#ifndef _GLIBCXX_TESTSUITE_CONTAINER_GEN_H
+#define _GLIBCXX_TESTSUITE_CONTAINER_GEN_H
+
+#include <cassert>
+#include <testsuite_container_traits.h>
+
+// Container requirement testing.
+namespace __gnu_test
+{
+
+
+  template<typename ContainerType, typename Tester, typename RandomGen>
+    void test_single_container(Tester test, RandomGen& rg, int length, int domain)
+    {
+      std::vector<int> values;
+      for(int i = 0; i < length; ++i)
+	{
+	  values.push_back(rg() % domain);
+	}
+
+      ContainerType con(values.data(), values.data() + length);
+      test(con, rg);
+    }
+
+  template<typename ContainerType, typename Tester, typename RandomGen>
+    void test_special_containers(Tester test, RandomGen& rg, int length)
+    {
+      std::vector<int> values(length);
+      ContainerType con(values.data(), values.data() + length);
+      for(int i = 0; i < length; ++i)
+	{
+	  values[i] = 0;
+	}
+      test(con, rg);
+
+      for(int i = 0; i < length; ++i)
+	{
+	  values[i] = i;
+	}
+      test(con, rg);
+
+      for(int i = 0; i < length; ++i)
+	{
+	  values[i] = -i;
+	}
+      test(con, rg);
+
+    }
+
+  template<typename ContainerType, typename Tester>
+    void test_containers(Tester test)
+    {
+      std::mt19937_64 random_gen;
+      
+#ifdef SIMULATOR_TEST
+      int loops = 10;
+#else
+      int loops = 1000;
+#endif
+
+      for(int i = 0; i < loops; ++i)
+	{
+	  test_special_containers<ContainerType>(test, random_gen, i);
+	}
+
+      for(int i = 1; i < 100; ++i)
+	for(int j = 0; j < loops; ++j)
+	{
+	  test_single_container<ContainerType>(test, random_gen, i, i);
+	}
+
+      
+      for(int i = 0; i < loops; ++i)
+	{
+	  test_single_container<ContainerType>(test, random_gen, 10, 10);
+	  test_single_container<ContainerType>(test, random_gen, 100, 10);
+	  test_single_container<ContainerType>(test, random_gen, 1000, 10);
+	  test_single_container<ContainerType>(test, random_gen, 10, 1000);
+	}
+
+#ifndef SIMULATOR_TEST
+      for(int i = 0; i < 1000; ++i)
+	{
+	  test_single_container<ContainerType>(test, random_gen, 10000, 10);	 
+	  test_single_container<ContainerType>(test, random_gen, 10000, 100000);
+	}
+#endif
+    }
+} // namespace __gnu_test
+
+#endif
Index: testsuite/util/testsuite_iterators.h
===================================================================
--- testsuite/util/testsuite_iterators.h	(revision 203853)
+++ testsuite/util/testsuite_iterators.h	(working copy)
@@ -539,6 +539,10 @@
       return ItType<T>(pos, &bounds);
     }
 
+    const T&
+    val(int pos)
+    { return (bounds.first)[pos]; }
+
     ItType<T>
     begin()
     { return it(bounds.first); }

--- gcc-4.8.2/libstdc++-v3/include/bits/stl_algo-orig.h	2016-03-20 12:45:17.518772229 +0900
+++ gcc-4.8.2/libstdc++-v3/include/bits/stl_algo.h	2016-03-20 12:46:36.073117985 +0900
@@ -2279,7 +2279,7 @@
 				_RandomAccessIterator __last)
     {
       _RandomAccessIterator __mid = __first + (__last - __first) / 2;
-      std::__move_median_to_first(__first, __first + 1, __mid, (__last - 2));
+      std::__move_median_to_first(__first, __first + 1, __mid, (__last - 1));
       return std::__unguarded_partition(__first + 1, __last, *__first);
     }