Restructure test suite to follow libc++ standard layout

Summary: Subsumes changes requested in https://reviews.llvm.org/D59110

Reviewers: EricWF, ldionne

Subscribers: mgorny, krytarowski, jfb, jdoerfert, libcxx-commits

Differential Revision: https://reviews.llvm.org/D59856

llvm-svn: 357124

9 files changed, 1509 insertions, 0 deletions

diff --git a/pstl/test/std/algorithms/alg.sorting/alg.heap.operations/is_heap.pass.cpp b/pstl/test/std/algorithms/alg.sorting/alg.heap.operations/is_heap.pass.cpp
new file mode 100644
index 00000000000..0c70342426e
--- /dev/null
+++ b/pstl/test/std/algorithms/alg.sorting/alg.heap.operations/is_heap.pass.cpp
@@ -0,0 +1,148 @@
+// -*- C++ -*-
+//===-- is_heap.pass.cpp --------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// Tests for is_heap, is_heap_until
+#include "support/pstl_test_config.h"
+
+#ifdef PSTL_STANDALONE_TESTS
+#include "pstl/execution"
+#include "pstl/algorithm"
+#else
+#include <execution>
+#include <algorithm>
+#endif // PSTL_STANDALONE_TESTS
+
+#include "support/utils.h"
+#include <iostream>
+
+using namespace TestUtils;
+
+struct WithCmpOp
+{
+    int32_t _first;
+    int32_t _second;
+    WithCmpOp() : _first(0), _second(0){};
+    explicit WithCmpOp(int32_t x) : _first(x), _second(x){};
+    bool
+    operator<(const WithCmpOp& rhs) const
+    {
+        return this->_first < rhs._first;
+    }
+};
+
+struct test_is_heap
+{
+#if __PSTL_ICC_17_VC141_TEST_SIMD_LAMBDA_DEBUG_32_BROKEN ||                                                            \
+    __PSTL_ICC_16_VC14_TEST_SIMD_LAMBDA_DEBUG_32_BROKEN //dummy specialization by policy type, in case of broken configuration
+    template <typename Iterator, typename Predicate>
+    typename std::enable_if<is_same_iterator_category<Iterator, std::random_access_iterator_tag>::value, void>::type
+    operator()(pstl::execution::unsequenced_policy, Iterator first, Iterator last, Predicate pred)
+    {
+    }
+    template <typename Iterator, typename Predicate>
+    typename std::enable_if<is_same_iterator_category<Iterator, std::random_access_iterator_tag>::value, void>::type
+    operator()(pstl::execution::parallel_unsequenced_policy, Iterator first, Iterator last, Predicate pred)
+    {
+    }
+#endif
+
+    template <typename Policy, typename Iterator, typename Predicate>
+    typename std::enable_if<is_same_iterator_category<Iterator, std::random_access_iterator_tag>::value, void>::type
+    operator()(Policy&& exec, Iterator first, Iterator last, Predicate pred)
+    {
+        using namespace std;
+        // is_heap
+        {
+            bool expected = is_heap(first, last);
+            bool actual = is_heap(exec, first, last);
+            EXPECT_TRUE(expected == actual, "wrong return value from is_heap");
+        }
+        // is_heap with predicate
+        {
+            bool expected = is_heap(first, last, pred);
+            bool actual = is_heap(exec, first, last, pred);
+            EXPECT_TRUE(expected == actual, "wrong return value from is_heap with predicate");
+        }
+        // is_heap_until
+        {
+            Iterator expected = is_heap_until(first, last);
+            Iterator actual = is_heap_until(exec, first, last);
+            EXPECT_TRUE(expected == actual, "wrong return value from is_heap_until");
+        }
+        // is_heap_until with predicate
+        {
+            const Iterator expected = is_heap_until(first, last, pred);
+            const auto y = std::distance(first, expected);
+            const Iterator actual = is_heap_until(exec, first, last, pred);
+            const auto x = std::distance(first, actual);
+            EXPECT_TRUE(expected == actual, "wrong return value from is_heap_until with predicate");
+        }
+    }
+
+    // is_heap, is_heap_until works only with random access iterators
+    template <typename Policy, typename Iterator, typename Predicate>
+    typename std::enable_if<!is_same_iterator_category<Iterator, std::random_access_iterator_tag>::value, void>::type
+    operator()(Policy&& exec, Iterator first, Iterator last, Predicate pred)
+    {
+    }
+};
+
+template <typename T, typename Comp>
+void
+test_is_heap_by_type(Comp comp)
+{
+    using namespace std;
+
+    const size_t max_size = 100000;
+    for (size_t n = 0; n <= max_size; n = n <= 16 ? n + 1 : size_t(3.1415 * n))
+    {
+        Sequence<T> in(n, [](size_t v) -> T { return T(v); });
+
+        invoke_on_all_policies(test_is_heap(), in.begin(), in.end(), comp);
+
+        std::make_heap(in.begin(), in.begin() + n / 4, comp);
+        invoke_on_all_policies(test_is_heap(), in.cbegin(), in.cend(), comp);
+
+        std::make_heap(in.begin(), in.begin() + n / 3, comp);
+        invoke_on_all_policies(test_is_heap(), in.begin(), in.end(), comp);
+
+        std::make_heap(in.begin(), in.end(), comp);
+        invoke_on_all_policies(test_is_heap(), in.cbegin(), in.cend(), comp);
+    }
+
+    Sequence<T> in(max_size / 10, [](size_t v) -> T { return T(1); });
+    invoke_on_all_policies(test_is_heap(), in.begin(), in.end(), comp);
+}
+
+template <typename T>
+struct test_non_const
+{
+    template <typename Policy, typename Iterator>
+    void
+    operator()(Policy&& exec, Iterator iter)
+    {
+        invoke_if(exec, [&]() {
+            is_heap(exec, iter, iter, non_const(std::less<T>()));
+            is_heap_until(exec, iter, iter, non_const(std::less<T>()));
+        });
+    }
+};
+
+int32_t
+main()
+{
+    test_is_heap_by_type<float32_t>(std::greater<float32_t>());
+    test_is_heap_by_type<WithCmpOp>(std::less<WithCmpOp>());
+    test_is_heap_by_type<uint64_t>([](uint64_t x, uint64_t y) { return x % 100 < y % 100; });
+
+    test_algo_basic_single<int32_t>(run_for_rnd<test_non_const<int32_t>>());
+
+    std::cout << done() << std::endl;
+    return 0;
+}
diff --git a/pstl/test/std/algorithms/alg.sorting/alg.lex.comparison/lexicographical_compare.pass.cpp b/pstl/test/std/algorithms/alg.sorting/alg.lex.comparison/lexicographical_compare.pass.cpp
new file mode 100644
index 00000000000..236e34290ae
--- /dev/null
+++ b/pstl/test/std/algorithms/alg.sorting/alg.lex.comparison/lexicographical_compare.pass.cpp
@@ -0,0 +1,179 @@
+// -*- C++ -*-
+//===-- lexicographical_compare.pass.cpp ----------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "support/pstl_test_config.h"
+
+#ifdef PSTL_STANDALONE_TESTS
+#include <iostream>
+
+#include "pstl/execution"
+#include "pstl/algorithm"
+#else
+#include <execution>
+#include <algorithm>
+#endif // PSTL_STANDALONE_TESTS
+
+#include "support/utils.h"
+
+using namespace TestUtils;
+
+struct test_one_policy
+{
+
+    template <typename ExecutionPolicy, typename Iterator1, typename Iterator2, typename Predicate>
+    void
+    operator()(ExecutionPolicy&& exec, Iterator1 begin1, Iterator1 end1, Iterator2 begin2, Iterator2 end2,
+               Predicate pred)
+    {
+        const bool expected = std::lexicographical_compare(begin1, end1, begin2, end2, pred);
+        const bool actual = std::lexicographical_compare(exec, begin1, end1, begin2, end2, pred);
+        EXPECT_TRUE(actual == expected, "wrong return result from lexicographical compare with predicate");
+    }
+
+    template <typename ExecutionPolicy, typename Iterator1, typename Iterator2>
+    void
+    operator()(ExecutionPolicy&& exec, Iterator1 begin1, Iterator1 end1, Iterator2 begin2, Iterator2 end2)
+    {
+        const bool expected = std::lexicographical_compare(begin1, end1, begin2, end2);
+        const bool actual = std::lexicographical_compare(exec, begin1, end1, begin2, end2);
+        EXPECT_TRUE(actual == expected, "wrong return result from lexicographical compare without predicate");
+    }
+};
+
+template <typename T1, typename T2, typename Predicate>
+void
+test(Predicate pred)
+{
+
+    const std::size_t max_n = 1000000;
+    Sequence<T1> in1(max_n, [](std::size_t k) { return T1(k); });
+    Sequence<T2> in2(2 * max_n, [](std::size_t k) { return T2(k); });
+
+    std::size_t n2;
+
+    // Test case: Call algorithm's version without predicate.
+    invoke_on_all_policies(test_one_policy(), in1.cbegin(), in1.cbegin() + max_n, in2.cbegin() + 3 * max_n / 10,
+                           in2.cbegin() + 5 * max_n / 10);
+
+    // Test case: If one range is a prefix of another, the shorter range is lexicographically less than the other.
+    std::size_t max_n2 = max_n / 10;
+    invoke_on_all_policies(test_one_policy(), in1.begin(), in1.begin() + max_n, in2.cbegin(), in2.cbegin() + max_n2,
+                           pred);
+    invoke_on_all_policies(test_one_policy(), in1.begin(), in1.begin() + max_n, in2.begin() + max_n2,
+                           in2.begin() + 3 * max_n2, pred);
+
+    // Test case: If one range is a prefix of another, the shorter range is lexicographically less than the other.
+    max_n2 = 2 * max_n;
+    invoke_on_all_policies(test_one_policy(), in1.cbegin(), in1.cbegin() + max_n, in2.begin(), in2.begin() + max_n2,
+                           pred);
+
+    for (std::size_t n1 = 0; n1 <= max_n; n1 = n1 <= 16 ? n1 + 1 : std::size_t(3.1415 * n1))
+    {
+        // Test case: If two ranges have equivalent elements and are of the same length, then the ranges are lexicographically equal.
+        n2 = n1;
+        invoke_on_all_policies(test_one_policy(), in1.begin(), in1.begin() + n1, in2.begin(), in2.begin() + n2, pred);
+
+        n2 = n1;
+        // Test case: two ranges have different elements and are of the same length (second sequence less than first)
+        std::size_t ind = n1 / 2;
+        in2[ind] = T2(-1);
+        invoke_on_all_policies(test_one_policy(), in1.begin(), in1.begin() + n1, in2.begin(), in2.begin() + n2, pred);
+        in2[ind] = T2(ind);
+
+        // Test case: two ranges have different elements and are of the same length (first sequence less than second)
+        ind = n1 / 5;
+        in1[ind] = T1(-1);
+        invoke_on_all_policies(test_one_policy(), in1.begin(), in1.begin() + n1, in2.cbegin(), in2.cbegin() + n2, pred);
+        in1[ind] = T1(ind);
+    }
+}
+
+template <typename Predicate>
+void
+test_string(Predicate pred)
+{
+
+    const std::size_t max_n = 1000000;
+    std::string in1 = "";
+    std::string in2 = "";
+    for (std::size_t n1 = 0; n1 <= max_n; ++n1)
+    {
+        in1 += n1;
+    }
+
+    for (std::size_t n1 = 0; n1 <= 2 * max_n; ++n1)
+    {
+        in2 += n1;
+    }
+
+    std::size_t n2;
+
+    for (std::size_t n1 = 0; n1 < in1.size(); n1 = n1 <= 16 ? n1 + 1 : std::size_t(3.1415 * n1))
+    {
+        // Test case: If two ranges have equivalent elements and are of the same length, then the ranges are lexicographically equal.
+        n2 = n1;
+        invoke_on_all_policies(test_one_policy(), in1.begin(), in1.begin() + n1, in2.begin(), in2.begin() + n2, pred);
+
+        n2 = n1;
+        // Test case: two ranges have different elements and are of the same length (second sequence less than first)
+        in2[n1 / 2] = 'a';
+        invoke_on_all_policies(test_one_policy(), in1.begin(), in1.begin() + n1, in2.begin(), in2.begin() + n2, pred);
+
+        // Test case: two ranges have different elements and are of the same length (first sequence less than second)
+        in1[n1 / 5] = 'a';
+        invoke_on_all_policies(test_one_policy(), in1.begin(), in1.begin() + n1, in2.cbegin(), in2.cbegin() + n2, pred);
+    }
+    invoke_on_all_policies(test_one_policy(), in1.cbegin(), in1.cbegin() + max_n, in2.cbegin() + 3 * max_n / 10,
+                           in2.cbegin() + 5 * max_n / 10);
+}
+
+template <typename T>
+struct LocalWrapper
+{
+    explicit LocalWrapper(std::size_t k) : my_val(k) {}
+    bool
+    operator<(const LocalWrapper<T>& w) const
+    {
+        return my_val < w.my_val;
+    }
+
+  private:
+    T my_val;
+};
+
+template <typename T>
+struct test_non_const
+{
+    template <typename Policy, typename FirstIterator, typename SecondInterator>
+    void
+    operator()(Policy&& exec, FirstIterator first_iter, SecondInterator second_iter)
+    {
+        invoke_if(exec, [&]() {
+            lexicographical_compare(exec, first_iter, first_iter, second_iter, second_iter, non_const(std::less<T>()));
+        });
+    }
+};
+
+int32_t
+main()
+{
+    test<uint16_t, float64_t>(std::less<float64_t>());
+    test<float32_t, int32_t>(std::greater<float32_t>());
+#if !__PSTL_ICC_18_TEST_EARLY_EXIT_AVX_RELEASE_BROKEN
+    test<float64_t, int32_t>([](const float64_t x, const int32_t y) { return x * x < y * y; });
+#endif
+    test<LocalWrapper<int32_t>, LocalWrapper<int32_t>>(
+        [](const LocalWrapper<int32_t>& x, const LocalWrapper<int32_t>& y) { return x < y; });
+    test_string([](const char x, const char y) { return x < y; });
+
+    test_algo_basic_double<int32_t>(run_for_rnd_fw<test_non_const<int32_t>>());
+
+    std::cout << done() << std::endl;
+    return 0;
+}
diff --git a/pstl/test/std/algorithms/alg.sorting/alg.min.max/minmax_element.pass.cpp b/pstl/test/std/algorithms/alg.sorting/alg.min.max/minmax_element.pass.cpp
new file mode 100644
index 00000000000..e3fec868375
--- /dev/null
+++ b/pstl/test/std/algorithms/alg.sorting/alg.min.max/minmax_element.pass.cpp
@@ -0,0 +1,198 @@
+// -*- C++ -*-
+//===-- minmax_element.pass.cpp -------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "support/pstl_test_config.h"
+
+#ifdef PSTL_STANDALONE_TESTS
+
+#include "pstl/execution"
+#include "pstl/algorithm"
+#else
+#include <execution>
+#include <algorithm>
+#endif // PSTL_STANDALONE_TESTS
+
+#include "support/utils.h"
+
+#include <set>
+#include <cassert>
+#include <cmath>
+
+using namespace TestUtils;
+
+struct check_minelement
+{
+    template <typename Policy, typename Iterator>
+    void
+    operator()(Policy&& exec, Iterator begin, Iterator end)
+    {
+        typedef typename std::iterator_traits<Iterator>::value_type T;
+        const Iterator expect = std::min_element(begin, end);
+        const Iterator result = std::min_element(exec, begin, end);
+        const Iterator result_pred = std::min_element(exec, begin, end, std::less<T>());
+        EXPECT_TRUE(expect == result, "wrong return result from min_element");
+        EXPECT_TRUE(expect == result_pred, "wrong return result from min_element");
+    }
+};
+
+struct check_maxelement
+{
+    template <typename Policy, typename Iterator>
+    void
+    operator()(Policy&& exec, Iterator begin, Iterator end)
+    {
+        typedef typename std::iterator_traits<Iterator>::value_type T;
+        const Iterator expect = std::max_element(begin, end);
+        const Iterator result = std::max_element(exec, begin, end);
+        const Iterator result_pred = std::max_element(exec, begin, end, std::less<T>());
+        EXPECT_TRUE(expect == result, "wrong return result from max_element");
+        EXPECT_TRUE(expect == result_pred, "wrong return result from max_element");
+    }
+};
+
+struct check_minmaxelement
+{
+    template <typename Policy, typename Iterator>
+    void
+    operator()(Policy&& exec, Iterator begin, Iterator end)
+    {
+        typedef typename std::iterator_traits<Iterator>::value_type T;
+        const std::pair<Iterator, Iterator> expect = std::minmax_element(begin, end);
+        const std::pair<Iterator, Iterator> got = std::minmax_element(exec, begin, end);
+        const std::pair<Iterator, Iterator> got_pred = std::minmax_element(exec, begin, end, std::less<T>());
+        EXPECT_TRUE(expect.first == got.first, "wrong return result from minmax_element (min part)");
+        EXPECT_TRUE(expect.second == got.second, "wrong return result from minmax_element (max part)");
+        EXPECT_TRUE(expect == got_pred, "wrong return result from minmax_element");
+    }
+};
+
+template <typename T>
+struct sequence_wrapper
+{
+    TestUtils::Sequence<T> seq;
+    const T min_value;
+    const T max_value;
+    static const std::size_t bits = 30; // We assume that T can handle signed 2^bits+1 value
+
+    // TestUtils::HashBits returns value between 0 and (1<<bits)-1,
+    // therefore we could threat 1<<bits as maximum and -(1<<bits) as a minimum
+    sequence_wrapper(std::size_t n) : seq(n), min_value(-(1 << bits)), max_value(1 << bits) {}
+
+    void
+    pattern_fill()
+    {
+        seq.fill([](std::size_t i) -> T { return T(TestUtils::HashBits(i, bits)); });
+    }
+
+    // sets first one at position `at` and bunch of them farther
+    void
+    set_desired_value(std::size_t at, T value)
+    {
+        if (seq.size() == 0)
+            return;
+        seq[at] = value;
+
+        //Producing serveral red herrings
+        for (std::size_t i = at + 1; i < seq.size(); i += 1 + TestUtils::HashBits(i, 5))
+            seq[i] = value;
+    }
+};
+
+template <typename T>
+void
+test_by_type(std::size_t n)
+{
+    sequence_wrapper<T> wseq(n);
+
+    // to avoid overtesing we use std::set to leave only unique indexes
+    std::set<std::size_t> targets{0};
+    if (n > 1)
+    {
+        targets.insert(1);
+        targets.insert(2.718282 * n / 3);
+        targets.insert(n / 2);
+        targets.insert(n / 7.389056);
+        targets.insert(n - 1); // last
+    }
+
+    for (std::set<std::size_t>::iterator it = targets.begin(); it != targets.end(); ++it)
+    {
+        wseq.pattern_fill();
+        wseq.set_desired_value(*it, wseq.min_value);
+        TestUtils::invoke_on_all_policies(check_minelement(), wseq.seq.cbegin(), wseq.seq.cend());
+        TestUtils::invoke_on_all_policies(check_minelement(), wseq.seq.begin(), wseq.seq.end());
+
+        wseq.set_desired_value(*it, wseq.max_value);
+        TestUtils::invoke_on_all_policies(check_maxelement(), wseq.seq.cbegin(), wseq.seq.cend());
+        TestUtils::invoke_on_all_policies(check_maxelement(), wseq.seq.begin(), wseq.seq.end());
+
+        if (targets.size() > 1)
+        {
+            for (std::set<std::size_t>::reverse_iterator rit = targets.rbegin(); rit != targets.rend(); ++rit)
+            {
+                if (*rit == *it) // we requires at least 2 unique indexes in targets
+                    break;
+                wseq.pattern_fill();
+                wseq.set_desired_value(*it, wseq.min_value);  // setting minimum element
+                wseq.set_desired_value(*rit, wseq.max_value); // setting maximum element
+                TestUtils::invoke_on_all_policies(check_minmaxelement(), wseq.seq.cbegin(), wseq.seq.cend());
+                TestUtils::invoke_on_all_policies(check_minmaxelement(), wseq.seq.begin(), wseq.seq.end());
+            }
+        }
+        else
+        { // we must check this corner case; it can not be tested in loop above
+            TestUtils::invoke_on_all_policies(check_minmaxelement(), wseq.seq.cbegin(), wseq.seq.cend());
+            TestUtils::invoke_on_all_policies(check_minmaxelement(), wseq.seq.begin(), wseq.seq.end());
+        }
+    }
+}
+
+// should provide minimal requirements only
+struct OnlyLessCompare
+{
+    int32_t val;
+    OnlyLessCompare() : val(0) {}
+    OnlyLessCompare(int32_t val_) : val(val_) {}
+    bool
+    operator<(const OnlyLessCompare& other) const
+    {
+        return val < other.val;
+    }
+};
+
+template <typename T>
+struct test_non_const
+{
+    template <typename Policy, typename Iterator>
+    void
+    operator()(Policy&& exec, Iterator iter)
+    {
+        max_element(exec, iter, iter, non_const(std::less<T>()));
+        min_element(exec, iter, iter, non_const(std::less<T>()));
+        minmax_element(exec, iter, iter, non_const(std::less<T>()));
+    }
+};
+
+int32_t
+main()
+{
+    using TestUtils::float64_t;
+    const std::size_t N = 100000;
+
+    for (std::size_t n = 0; n < N; n = n < 16 ? n + 1 : size_t(3.14159 * n))
+    {
+        test_by_type<float64_t>(n);
+        test_by_type<OnlyLessCompare>(n);
+    }
+
+    test_algo_basic_single<int32_t>(run_for_rnd_fw<test_non_const<int32_t>>());
+
+    std::cout << TestUtils::done() << std::endl;
+    return 0;
+}
diff --git a/pstl/test/std/algorithms/alg.sorting/alg.set.operations/includes.pass.cpp b/pstl/test/std/algorithms/alg.sorting/alg.set.operations/includes.pass.cpp
new file mode 100644
index 00000000000..b18bb5f69f0
--- /dev/null
+++ b/pstl/test/std/algorithms/alg.sorting/alg.set.operations/includes.pass.cpp
@@ -0,0 +1,111 @@
+// -*- C++ -*-
+//===-- includes.pass.cpp -------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "support/pstl_test_config.h"
+
+#ifdef PSTL_STANDALONE_TESTS
+
+#include <cmath>
+
+#include "pstl/execution"
+#include "pstl/algorithm"
+#else
+#include <execution>
+#include <algorithm>
+#endif // PSTL_STANDALONE_TESTS
+
+#include "support/utils.h"
+
+using namespace TestUtils;
+
+template <typename T>
+struct Num
+{
+    T val;
+    explicit Num(const T& v) : val(v) {}
+
+    //for "includes" checks
+    template <typename T1>
+    bool
+    operator<(const Num<T1>& v1) const
+    {
+        return val < v1.val;
+    }
+
+    //The types Type1 and Type2 must be such that an object of type InputIt can be dereferenced and then implicitly converted to both of them
+    template <typename T1>
+    operator Num<T1>() const
+    {
+        return Num<T1>((T1)val);
+    }
+};
+
+struct test_one_policy
+{
+    template <typename Policy, typename InputIterator1, typename InputIterator2, typename Compare>
+    typename std::enable_if<!TestUtils::isReverse<InputIterator1>::value, void>::type
+    operator()(Policy&& exec, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2,
+               Compare comp)
+    {
+
+        auto expect_res = std::includes(first1, last1, first2, last2, comp);
+        auto res = std::includes(exec, first1, last1, first2, last2, comp);
+
+        EXPECT_TRUE(expect_res == res, "wrong result for includes");
+    }
+
+    template <typename Policy, typename InputIterator1, typename InputIterator2, typename Compare>
+    typename std::enable_if<TestUtils::isReverse<InputIterator1>::value, void>::type
+    operator()(Policy&& exec, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2,
+               Compare comp)
+    {
+    }
+};
+
+template <typename T1, typename T2, typename Compare>
+void
+test_includes(Compare compare)
+{
+
+    const std::size_t n_max = 1000000;
+
+    // The rand()%(2*n+1) encourages generation of some duplicates.
+    std::srand(42);
+
+    for (std::size_t n = 0; n < n_max; n = n <= 16 ? n + 1 : size_t(3.1415 * n))
+    {
+        for (std::size_t m = 0; m < n_max; m = m <= 16 ? m + 1 : size_t(2.71828 * m))
+        {
+            //prepare the input ranges
+            Sequence<T1> in1(n, [](std::size_t k) { return rand() % (2 * k + 1); });
+            Sequence<T2> in2(m, [](std::size_t k) { return rand() % (k + 1); });
+
+            std::sort(in1.begin(), in1.end(), compare);
+            std::sort(in2.begin(), in2.end(), compare);
+
+            invoke_on_all_policies(test_one_policy(), in1.begin(), in1.end(), in2.cbegin(), in2.cend(), compare);
+
+            //test w/ non constant predicate
+            if (n < 5 && m < 5)
+                invoke_on_all_policies(test_one_policy(), in1.begin(), in1.end(), in2.cbegin(), in2.cend(),
+                                       non_const(compare));
+        }
+    }
+}
+
+int32_t
+main()
+{
+
+    test_includes<float64_t, float64_t>(__pstl::internal::pstl_less());
+    test_includes<Num<int64_t>, Num<int32_t>>([](const Num<int64_t>& x, const Num<int32_t>& y) { return x < y; });
+    std::cout << done() << std::endl;
+
+    return 0;
+}
diff --git a/pstl/test/std/algorithms/alg.sorting/alg.set.operations/set.pass.cpp b/pstl/test/std/algorithms/alg.sorting/alg.set.operations/set.pass.cpp
new file mode 100644
index 00000000000..33b7542d4fa
--- /dev/null
+++ b/pstl/test/std/algorithms/alg.sorting/alg.set.operations/set.pass.cpp
@@ -0,0 +1,167 @@
+// -*- C++ -*-
+//===-- set.pass.cpp ------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "support/pstl_test_config.h"
+
+#ifdef PSTL_STANDALONE_TESTS
+
+#include <cmath>
+#include <chrono>
+
+#include "pstl/execution"
+#include "pstl/algorithm"
+#else
+#include <execution>
+#include <algorithm>
+#endif // PSTL_STANDALONE_TESTS
+
+#include "support/utils.h"
+
+using namespace TestUtils;
+
+template <typename T>
+struct Num
+{
+    T val;
+
+    Num() : val{} {}
+    Num(const T& v) : val(v) {}
+
+    //for "includes" checks
+    template <typename T1>
+    bool
+    operator<(const Num<T1>& v1) const
+    {
+        return val < v1.val;
+    }
+
+    //The types Type1 and Type2 must be such that an object of type InputIt can be dereferenced and then implicitly converted to both of them
+    template <typename T1>
+    operator Num<T1>() const
+    {
+        return Num<T1>((T1)val);
+    }
+
+    friend bool
+    operator==(const Num& v1, const Num& v2)
+    {
+        return v1.val == v2.val;
+    }
+};
+
+struct test_one_policy
+{
+    template <typename Policy, typename InputIterator1, typename InputIterator2, typename Compare>
+    typename std::enable_if<!TestUtils::isReverse<InputIterator1>::value, void>::type
+    operator()(Policy&& exec, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2,
+               Compare comp)
+    {
+        using T1 = typename std::iterator_traits<InputIterator1>::value_type;
+
+        auto n1 = std::distance(first1, last1);
+        auto n2 = std::distance(first2, last2);
+        auto n = n1 + n2;
+        Sequence<T1> expect(n);
+        Sequence<T1> out(n);
+
+        //1. set_union
+        auto expect_res = std::set_union(first1, last1, first2, last2, expect.begin(), comp);
+        auto res = std::set_union(exec, first1, last1, first2, last2, out.begin(), comp);
+
+        EXPECT_TRUE(expect_res - expect.begin() == res - out.begin(), "wrong result for set_union");
+        EXPECT_EQ_N(expect.begin(), out.begin(), std::distance(out.begin(), res), "wrong set_union effect");
+
+        //2. set_intersection
+        expect_res = std::set_intersection(first1, last1, first2, last2, expect.begin(), comp);
+        res = std::set_intersection(exec, first1, last1, first2, last2, out.begin(), comp);
+
+        EXPECT_TRUE(expect_res - expect.begin() == res - out.begin(), "wrong result for set_intersection");
+        EXPECT_EQ_N(expect.begin(), out.begin(), std::distance(out.begin(), res), "wrong set_intersection effect");
+
+        //3. set_difference
+        expect_res = std::set_difference(first1, last1, first2, last2, expect.begin(), comp);
+        res = std::set_difference(exec, first1, last1, first2, last2, out.begin(), comp);
+
+        EXPECT_TRUE(expect_res - expect.begin() == res - out.begin(), "wrong result for set_difference");
+        EXPECT_EQ_N(expect.begin(), out.begin(), std::distance(out.begin(), res), "wrong set_difference effect");
+
+        //4. set_symmetric_difference
+        expect_res = std::set_symmetric_difference(first1, last1, first2, last2, expect.begin(), comp);
+        res = std::set_symmetric_difference(exec, first1, last1, first2, last2, out.begin(), comp);
+
+        EXPECT_TRUE(expect_res - expect.begin() == res - out.begin(), "wrong result for set_symmetric_difference");
+        EXPECT_EQ_N(expect.begin(), out.begin(), std::distance(out.begin(), res),
+                    "wrong set_symmetric_difference effect");
+    }
+
+    template <typename Policy, typename InputIterator1, typename InputIterator2, typename Compare>
+    typename std::enable_if<TestUtils::isReverse<InputIterator1>::value, void>::type
+    operator()(Policy&& exec, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2,
+               Compare comp)
+    {
+    }
+};
+
+template <typename T1, typename T2, typename Compare>
+void
+test_set(Compare compare)
+{
+
+    const std::size_t n_max = 100000;
+
+    // The rand()%(2*n+1) encourages generation of some duplicates.
+    std::srand(4200);
+
+    for (std::size_t n = 0; n < n_max; n = n <= 16 ? n + 1 : size_t(3.1415 * n))
+    {
+        for (std::size_t m = 0; m < n_max; m = m <= 16 ? m + 1 : size_t(2.71828 * m))
+        {
+            //prepare the input ranges
+            Sequence<T1> in1(n, [n](std::size_t k) { return rand() % (2 * k + 1); });
+            Sequence<T2> in2(m, [m](std::size_t k) { return (m % 2) * rand() + rand() % (k + 1); });
+
+            std::sort(in1.begin(), in1.end(), compare);
+            std::sort(in2.begin(), in2.end(), compare);
+
+            invoke_on_all_policies(test_one_policy(), in1.begin(), in1.end(), in2.cbegin(), in2.cend(), compare);
+        }
+    }
+}
+
+template <typename T>
+struct test_non_const
+{
+    template <typename Policy, typename InputIterator, typename OutputInterator>
+    void
+    operator()(Policy&& exec, InputIterator input_iter, OutputInterator out_iter)
+    {
+        set_difference(exec, input_iter, input_iter, input_iter, input_iter, out_iter, non_const(std::less<T>()));
+
+        set_intersection(exec, input_iter, input_iter, input_iter, input_iter, out_iter, non_const(std::less<T>()));
+
+        set_symmetric_difference(exec, input_iter, input_iter, input_iter, input_iter, out_iter,
+                                 non_const(std::less<T>()));
+
+        set_union(exec, input_iter, input_iter, input_iter, input_iter, out_iter, non_const(std::less<T>()));
+    }
+};
+
+int32_t
+main()
+{
+
+    test_set<float64_t, float64_t>(__pstl::internal::pstl_less());
+    test_set<Num<int64_t>, Num<int32_t>>([](const Num<int64_t>& x, const Num<int32_t>& y) { return x < y; });
+
+    test_algo_basic_double<int32_t>(run_for_rnd_fw<test_non_const<int32_t>>());
+
+    std::cout << done() << std::endl;
+
+    return 0;
+}
diff --git a/pstl/test/std/algorithms/alg.sorting/is_sorted.pass.cpp b/pstl/test/std/algorithms/alg.sorting/is_sorted.pass.cpp
new file mode 100644
index 00000000000..a5219f79669
--- /dev/null
+++ b/pstl/test/std/algorithms/alg.sorting/is_sorted.pass.cpp
@@ -0,0 +1,104 @@
+// -*- C++ -*-
+//===-- is_sorted.pass.cpp ------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "support/pstl_test_config.h"
+
+#ifdef PSTL_STANDALONE_TESTS
+
+#include "pstl/execution"
+#include "pstl/algorithm"
+#else
+#include <execution>
+#include <algorithm>
+#endif // PSTL_STANDALONE_TESTS
+
+#include "support/utils.h"
+
+using namespace TestUtils;
+
+struct test_is_sorted
+{
+    template <typename Policy, typename Iterator>
+    void
+    operator()(Policy&& exec, Iterator first, Iterator last, bool exam)
+    {
+        using namespace std;
+        typedef typename std::iterator_traits<Iterator>::value_type T;
+
+        //try random-access iterator
+        bool res = is_sorted(exec, first, last);
+        EXPECT_TRUE(exam == res, "is_sorted wrong result for random-access iterator");
+        auto iexam = is_sorted_until(first, last);
+        auto ires = is_sorted_until(exec, first, last);
+        EXPECT_TRUE(iexam == ires, "is_sorted_until wrong result for random-access iterator");
+
+        //try random-access iterator with a predicate
+        res = is_sorted(exec, first, last, std::less<T>());
+        EXPECT_TRUE(exam == res, "is_sorted wrong result for random-access iterator");
+        iexam = is_sorted_until(first, last, std::less<T>());
+        ires = is_sorted_until(exec, first, last, std::less<T>());
+        EXPECT_TRUE(iexam == ires, "is_sorted_until wrong result for random-access iterator");
+    }
+};
+
+template <typename T>
+void
+test_is_sorted_by_type()
+{
+
+    Sequence<T> in(99999, [](size_t v) -> T { return T(v); }); //fill 0..n
+
+    invoke_on_all_policies(test_is_sorted(), in.begin(), in.end(), std::is_sorted(in.begin(), in.end()));
+    invoke_on_all_policies(test_is_sorted(), in.cbegin(), in.cend(), std::is_sorted(in.begin(), in.end()));
+
+    in[in.size() / 2] = -1;
+    invoke_on_all_policies(test_is_sorted(), in.begin(), in.end(), std::is_sorted(in.begin(), in.end()));
+    invoke_on_all_policies(test_is_sorted(), in.cbegin(), in.cend(), std::is_sorted(in.begin(), in.end()));
+
+    in[1] = -1;
+    invoke_on_all_policies(test_is_sorted(), in.begin(), in.end(), std::is_sorted(in.begin(), in.end()));
+    invoke_on_all_policies(test_is_sorted(), in.cbegin(), in.cend(), std::is_sorted(in.begin(), in.end()));
+
+    //an empty container
+    Sequence<T> in0(0);
+    invoke_on_all_policies(test_is_sorted(), in0.begin(), in0.end(), std::is_sorted(in0.begin(), in0.end()));
+    invoke_on_all_policies(test_is_sorted(), in0.cbegin(), in0.cend(), std::is_sorted(in0.begin(), in0.end()));
+
+    //non-descending order
+    Sequence<T> in1(9, [](size_t v) -> T { return T(0); });
+    invoke_on_all_policies(test_is_sorted(), in1.begin(), in1.end(), std::is_sorted(in1.begin(), in1.end()));
+    invoke_on_all_policies(test_is_sorted(), in1.cbegin(), in1.cend(), std::is_sorted(in1.begin(), in1.end()));
+}
+
+template <typename T>
+struct test_non_const
+{
+    template <typename Policy, typename Iterator>
+    void
+    operator()(Policy&& exec, Iterator iter)
+    {
+        is_sorted(exec, iter, iter, std::less<T>());
+        is_sorted_until(exec, iter, iter, std::less<T>());
+    }
+};
+
+int32_t
+main()
+{
+
+    test_is_sorted_by_type<int32_t>();
+    test_is_sorted_by_type<float64_t>();
+
+    test_is_sorted_by_type<Wrapper<int32_t>>();
+
+    test_algo_basic_single<int32_t>(run_for_rnd_fw<test_non_const<int32_t>>());
+
+    std::cout << done() << std::endl;
+    return 0;
+}
diff --git a/pstl/test/std/algorithms/alg.sorting/partial_sort.pass.cpp b/pstl/test/std/algorithms/alg.sorting/partial_sort.pass.cpp
new file mode 100644
index 00000000000..6e9d7d21d66
--- /dev/null
+++ b/pstl/test/std/algorithms/alg.sorting/partial_sort.pass.cpp
@@ -0,0 +1,156 @@
+// -*- C++ -*-
+//===-- partial_sort.pass.cpp ---------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "support/pstl_test_config.h"
+
+#ifdef PSTL_STANDALONE_TESTS
+
+#include <cmath>
+
+#include "pstl/execution"
+#include "pstl/algorithm"
+#else
+#include <execution>
+#include <algorithm>
+#endif // PSTL_STANDALONE_TESTS
+
+#include "support/utils.h"
+
+using namespace TestUtils;
+
+static std::atomic<int32_t> count_val;
+static std::atomic<int32_t> count_comp;
+
+template <typename T>
+struct Num
+{
+    T val;
+
+    Num() { ++count_val; }
+    Num(T v) : val(v) { ++count_val; }
+    Num(const Num<T>& v) : val(v.val) { ++count_val; }
+    Num(Num<T>&& v) : val(v.val) { ++count_val; }
+    ~Num() { --count_val; }
+    Num<T>&
+    operator=(const Num<T>& v)
+    {
+        val = v.val;
+        return *this;
+    }
+    operator T() const { return val; }
+    bool
+    operator<(const Num<T>& v) const
+    {
+        ++count_comp;
+        return val < v.val;
+    }
+};
+
+struct test_brick_partial_sort
+{
+    template <typename Policy, typename InputIterator, typename Compare>
+    typename std::enable_if<is_same_iterator_category<InputIterator, std::random_access_iterator_tag>::value,
+                            void>::type
+    operator()(Policy&& exec, InputIterator first, InputIterator last, InputIterator exp_first, InputIterator exp_last,
+               Compare compare)
+    {
+
+        typedef typename std::iterator_traits<InputIterator>::value_type T;
+
+        // The rand()%(2*n+1) encourages generation of some duplicates.
+        std::srand(42);
+        const std::size_t n = last - first;
+        for (std::size_t k = 0; k < n; ++k)
+        {
+            first[k] = T(rand() % (2 * n + 1));
+        }
+        std::copy(first, last, exp_first);
+
+        for (std::size_t p = 0; p < n; p = p <= 16 ? p + 1 : std::size_t(31.415 * p))
+        {
+            auto m1 = first + p;
+            auto m2 = exp_first + p;
+
+            std::partial_sort(exp_first, m2, exp_last, compare);
+            count_comp = 0;
+            std::partial_sort(exec, first, m1, last, compare);
+            EXPECT_EQ_N(exp_first, first, p, "wrong effect from partial_sort");
+
+            //checking upper bound number of comparisons; O(p*(last-first)log(middle-first)); where p - number of threads;
+            if (m1 - first > 1)
+            {
+                auto complex = std::ceil(n * std::log(float32_t(m1 - first)));
+#if defined(__PSTL_PAR_BACKEND_TBB)
+                auto p = tbb::this_task_arena::max_concurrency();
+#else
+                auto p = 1;
+#endif
+
+#ifdef _DEBUG
+                if (count_comp > complex * p)
+                {
+                    std::cout << "complexity exceeded" << std::endl;
+                }
+#endif
+            }
+        }
+    }
+
+    template <typename Policy, typename InputIterator, typename Compare>
+    typename std::enable_if<!is_same_iterator_category<InputIterator, std::random_access_iterator_tag>::value,
+                            void>::type
+    operator()(Policy&& exec, InputIterator first, InputIterator last, InputIterator exp_first, InputIterator exp_last,
+               Compare compare)
+    {
+    }
+};
+
+template <typename T, typename Compare>
+void
+test_partial_sort(Compare compare)
+{
+
+    const std::size_t n_max = 100000;
+    Sequence<T> in(n_max);
+    Sequence<T> exp(n_max);
+    for (std::size_t n = 0; n < n_max; n = n <= 16 ? n + 1 : size_t(3.1415 * n))
+    {
+        invoke_on_all_policies(test_brick_partial_sort(), in.begin(), in.begin() + n, exp.begin(), exp.begin() + n,
+                               compare);
+    }
+}
+
+template <typename T>
+struct test_non_const
+{
+    template <typename Policy, typename Iterator>
+    void
+    operator()(Policy&& exec, Iterator iter)
+    {
+        partial_sort(exec, iter, iter, iter, non_const(std::less<T>()));
+    }
+};
+
+int32_t
+main()
+{
+    count_val = 0;
+
+    test_partial_sort<Num<float32_t>>([](Num<float32_t> x, Num<float32_t> y) { return x < y; });
+
+    EXPECT_TRUE(count_val == 0, "cleanup error");
+
+    test_partial_sort<int32_t>(
+        [](int32_t x, int32_t y) { return x > y; }); // Reversed so accidental use of < will be detected.
+
+    test_algo_basic_single<int32_t>(run_for_rnd<test_non_const<int32_t>>());
+
+    std::cout << done() << std::endl;
+    return 0;
+}
diff --git a/pstl/test/std/algorithms/alg.sorting/partial_sort_copy.pass.cpp b/pstl/test/std/algorithms/alg.sorting/partial_sort_copy.pass.cpp
new file mode 100644
index 00000000000..8f132022c64
--- /dev/null
+++ b/pstl/test/std/algorithms/alg.sorting/partial_sort_copy.pass.cpp
@@ -0,0 +1,195 @@
+// -*- C++ -*-
+//===-- partial_sort_copy.pass.cpp ----------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// Tests for partial_sort_copy
+
+#include <cmath>
+#include "support/pstl_test_config.h"
+
+#ifdef PSTL_STANDALONE_TESTS
+#include "pstl/execution"
+#include "pstl/algorithm"
+#else
+#include <execution>
+#include <algorithm>
+#endif // PSTL_STANDALONE_TESTS
+
+#include "support/utils.h"
+
+using namespace TestUtils;
+
+template <typename T>
+struct Num
+{
+    T val;
+
+    Num() : val(0) {}
+    Num(T v) : val(v) {}
+    Num(const Num<T>& v) : val(v.val) {}
+    Num(Num<T>&& v) : val(v.val) {}
+    Num<T>&
+    operator=(const Num<T>& v)
+    {
+        val = v.val;
+        return *this;
+    }
+    operator T() const { return val; }
+    bool
+    operator<(const Num<T>& v) const
+    {
+        return val < v.val;
+    }
+};
+
+template <typename RandomAccessIterator>
+struct test_one_policy
+{
+    RandomAccessIterator d_first;
+    RandomAccessIterator d_last;
+    RandomAccessIterator exp_first;
+    RandomAccessIterator exp_last;
+    // This ctor is needed because output shouldn't be transformed to any iterator type (only random access iterators are allowed)
+    test_one_policy(RandomAccessIterator b1, RandomAccessIterator e1, RandomAccessIterator b2, RandomAccessIterator e2)
+        : d_first(b1), d_last(e1), exp_first(b2), exp_last(e2)
+    {
+    }
+#if __PSTL_ICC_17_VC141_TEST_SIMD_LAMBDA_DEBUG_32_BROKEN ||                                                            \
+    __PSTL_ICC_16_VC14_TEST_SIMD_LAMBDA_DEBUG_32_BROKEN // dummy specialization by policy type, in case of broken configuration
+    template <typename InputIterator, typename Size, typename T, typename Compare>
+    void
+    operator()(pstl::execution::unsequenced_policy, InputIterator first, InputIterator last, Size n1, Size n2,
+               const T& trash, Compare compare)
+    {
+    }
+
+    template <typename InputIterator, typename Size, typename T, typename Compare>
+    void
+    operator()(pstl::execution::parallel_unsequenced_policy, InputIterator first, InputIterator last, Size n1, Size n2,
+               const T& trash, Compare compare)
+    {
+    }
+
+    template <typename InputIterator, typename Size, typename T>
+    void
+    operator()(pstl::execution::unsequenced_policy, InputIterator first, InputIterator last, Size n1, Size n2,
+               const T& trash)
+    {
+    }
+
+    template <typename InputIterator, typename Size, typename T>
+    void
+    operator()(pstl::execution::parallel_unsequenced_policy, InputIterator first, InputIterator last, Size n1, Size n2,
+               const T& trash)
+    {
+    }
+#endif
+
+    template <typename Policy, typename InputIterator, typename Size, typename T, typename Compare>
+    void
+    operator()(Policy&& exec, InputIterator first, InputIterator last, Size n1, Size n2, const T& trash,
+               Compare compare)
+    {
+        prepare_data(first, last, n1, trash);
+        RandomAccessIterator exp = std::partial_sort_copy(first, last, exp_first, exp_last, compare);
+        RandomAccessIterator res = std::partial_sort_copy(exec, first, last, d_first, d_last, compare);
+
+        EXPECT_TRUE((exp - exp_first) == (res - d_first), "wrong result from partial_sort_copy with predicate");
+        EXPECT_EQ_N(exp_first, d_first, n2, "wrong effect from partial_sort_copy with predicate");
+    }
+
+    template <typename Policy, typename InputIterator, typename Size, typename T>
+    void
+    operator()(Policy&& exec, InputIterator first, InputIterator last, Size n1, Size n2, const T& trash)
+    {
+        prepare_data(first, last, n1, trash);
+        RandomAccessIterator exp = std::partial_sort_copy(first, last, exp_first, exp_last);
+        RandomAccessIterator res = std::partial_sort_copy(exec, first, last, d_first, d_last);
+
+        EXPECT_TRUE((exp - exp_first) == (res - d_first), "wrong result from partial_sort_copy without predicate");
+        EXPECT_EQ_N(exp_first, d_first, n2, "wrong effect from partial_sort_copy without predicate");
+    }
+
+  private:
+    template <typename InputIterator, typename Size, typename T>
+    void
+    prepare_data(InputIterator first, InputIterator last, Size n1, const T& trash)
+    {
+        // The rand()%(2*n+1) encourages generation of some duplicates.
+        std::srand(42);
+        std::generate(first, last, [n1]() { return T(rand() % (2 * n1 + 1)); });
+
+        std::fill(exp_first, exp_last, trash);
+        std::fill(d_first, d_last, trash);
+    }
+};
+
+template <typename T, typename Compare>
+void
+test_partial_sort_copy(Compare compare)
+{
+
+    typedef typename Sequence<T>::iterator iterator_type;
+    const std::size_t n_max = 100000;
+    Sequence<T> in(n_max);
+    Sequence<T> out(2 * n_max);
+    Sequence<T> exp(2 * n_max);
+    std::size_t n1 = 0;
+    std::size_t n2;
+    T trash = T(-666);
+    for (; n1 < n_max; n1 = n1 <= 16 ? n1 + 1 : size_t(3.1415 * n1))
+    {
+        // If both sequences are equal
+        n2 = n1;
+        invoke_on_all_policies(
+            test_one_policy<iterator_type>(out.begin(), out.begin() + n2, exp.begin(), exp.begin() + n2), in.begin(),
+            in.begin() + n1, n1, n2, trash, compare);
+
+        // If first sequence is greater than second
+        n2 = n1 / 3;
+        invoke_on_all_policies(
+            test_one_policy<iterator_type>(out.begin(), out.begin() + n2, exp.begin(), exp.begin() + n2), in.begin(),
+            in.begin() + n1, n1, n2, trash, compare);
+
+        // If first sequence is less than second
+        n2 = 2 * n1;
+        invoke_on_all_policies(
+            test_one_policy<iterator_type>(out.begin(), out.begin() + n2, exp.begin(), exp.begin() + n2), in.begin(),
+            in.begin() + n1, n1, n2, trash, compare);
+    }
+    // Test partial_sort_copy without predicate
+    n1 = n_max;
+    n2 = 2 * n1;
+    invoke_on_all_policies(test_one_policy<iterator_type>(out.begin(), out.begin() + n2, exp.begin(), exp.begin() + n2),
+                           in.begin(), in.begin() + n1, n1, n2, trash);
+}
+
+template <typename T>
+struct test_non_const
+{
+    template <typename Policy, typename InputIterator, typename OutputInterator>
+    void
+    operator()(Policy&& exec, InputIterator input_iter, OutputInterator out_iter)
+    {
+        invoke_if(exec, [&]() {
+            partial_sort_copy(exec, input_iter, input_iter, out_iter, out_iter, non_const(std::less<T>()));
+        });
+    }
+};
+
+int32_t
+main()
+{
+    test_partial_sort_copy<Num<float32_t>>([](Num<float32_t> x, Num<float32_t> y) { return x < y; });
+    test_partial_sort_copy<int32_t>([](int32_t x, int32_t y) { return x > y; });
+
+    test_algo_basic_double<int32_t>(run_for_rnd<test_non_const<int32_t>>());
+
+    std::cout << done() << std::endl;
+    return 0;
+}
diff --git a/pstl/test/std/algorithms/alg.sorting/sort.pass.cpp b/pstl/test/std/algorithms/alg.sorting/sort.pass.cpp
new file mode 100644
index 00000000000..e2eb9cecd2d
--- /dev/null
+++ b/pstl/test/std/algorithms/alg.sorting/sort.pass.cpp
@@ -0,0 +1,251 @@
+// -*- C++ -*-
+//===-- sort.pass.cpp -----------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "support/pstl_test_config.h"
+
+#ifdef PSTL_STANDALONE_TESTS
+
+#include "pstl/execution"
+#include "pstl/algorithm"
+#else
+#include <execution>
+#include <algorithm>
+#endif // PSTL_STANDALONE_TESTS
+
+#include "support/utils.h"
+
+using namespace TestUtils;
+#define _CRT_SECURE_NO_WARNINGS
+
+#include <atomic>
+
+static bool Stable;
+
+//! Number of extant keys
+static std::atomic<int32_t> KeyCount;
+
+//! One more than highest index in array to be sorted.
+static uint32_t LastIndex;
+
+//! Keeping Equal() static and a friend of ParanoidKey class (C++, paragraphs 3.5/7.1.1)
+class ParanoidKey;
+static bool
+Equal(const ParanoidKey& x, const ParanoidKey& y);
+
+//! A key to be sorted, with lots of checking.
+class ParanoidKey
+{
+    //! Value used by comparator
+    int32_t value;
+    //! Original position or special value (Empty or Dead)
+    int32_t index;
+    //! Special value used to mark object without a comparable value, e.g. after being moved from.
+    static const int32_t Empty = -1;
+    //! Special value used to mark destroyed objects.
+    static const int32_t Dead = -2;
+    // True if key object has comparable value
+    bool
+    isLive() const
+    {
+        return (uint32_t)(index) < LastIndex;
+    }
+    // True if key object has been constructed.
+    bool
+    isConstructed() const
+    {
+        return isLive() || index == Empty;
+    }
+
+  public:
+    ParanoidKey()
+    {
+        ++KeyCount;
+        index = Empty;
+        value = Empty;
+    }
+    ParanoidKey(const ParanoidKey& k) : value(k.value), index(k.index)
+    {
+        EXPECT_TRUE(k.isLive(), "source for copy-constructor is dead");
+        ++KeyCount;
+    }
+    ~ParanoidKey()
+    {
+        EXPECT_TRUE(isConstructed(), "double destruction");
+        index = Dead;
+        --KeyCount;
+    }
+    ParanoidKey&
+    operator=(const ParanoidKey& k)
+    {
+        EXPECT_TRUE(k.isLive(), "source for copy-assignment is dead");
+        EXPECT_TRUE(isConstructed(), "destination for copy-assignment is dead");
+        value = k.value;
+        index = k.index;
+        return *this;
+    }
+    ParanoidKey(int32_t index, int32_t value, OddTag) : index(index), value(value) {}
+    ParanoidKey(ParanoidKey&& k) : value(k.value), index(k.index)
+    {
+        EXPECT_TRUE(k.isConstructed(), "source for move-construction is dead");
+// std::stable_sort() fails in move semantics on paranoid test before VS2015
+#if !defined(_MSC_VER) || _MSC_VER >= 1900
+        k.index = Empty;
+#endif
+        ++KeyCount;
+    }
+    ParanoidKey&
+    operator=(ParanoidKey&& k)
+    {
+        EXPECT_TRUE(k.isConstructed(), "source for move-assignment is dead");
+        EXPECT_TRUE(isConstructed(), "destination for move-assignment is dead");
+        value = k.value;
+        index = k.index;
+// std::stable_sort() fails in move semantics on paranoid test before VS2015
+#if !defined(_MSC_VER) || _MSC_VER >= 1900
+        k.index = Empty;
+#endif
+        return *this;
+    }
+    friend class KeyCompare;
+    friend bool
+    Equal(const ParanoidKey& x, const ParanoidKey& y);
+};
+
+class KeyCompare
+{
+    enum statusType
+    {
+        //! Special value used to mark defined object.
+        Live = 0xabcd,
+        //! Special value used to mark destroyed objects.
+        Dead = -1
+    } status;
+
+  public:
+    KeyCompare(OddTag) : status(Live) {}
+    ~KeyCompare() { status = Dead; }
+    bool
+    operator()(const ParanoidKey& j, const ParanoidKey& k) const
+    {
+        EXPECT_TRUE(status == Live, "key comparison object not defined");
+        EXPECT_TRUE(j.isLive(), "first key to operator() is not live");
+        EXPECT_TRUE(k.isLive(), "second key to operator() is not live");
+        return j.value < k.value;
+    }
+};
+
+// Equal is equality comparison used for checking result of sort against expected result.
+static bool
+Equal(const ParanoidKey& x, const ParanoidKey& y)
+{
+    return (x.value == y.value && !Stable) || (x.index == y.index);
+}
+
+static bool
+Equal(float32_t x, float32_t y)
+{
+    return x == y;
+}
+
+static bool
+Equal(int32_t x, int32_t y)
+{
+    return x == y;
+}
+
+struct test_sort_with_compare
+{
+    template <typename Policy, typename InputIterator, typename OutputIterator, typename OutputIterator2, typename Size,
+              typename Compare>
+    typename std::enable_if<is_same_iterator_category<InputIterator, std::random_access_iterator_tag>::value,
+                            void>::type
+    operator()(Policy&& exec, OutputIterator tmp_first, OutputIterator tmp_last, OutputIterator2 expected_first,
+               OutputIterator2 expected_last, InputIterator first, InputIterator last, Size n, Compare compare)
+    {
+        using namespace std;
+        copy_n(first, n, expected_first);
+        copy_n(first, n, tmp_first);
+        if (Stable)
+            std::stable_sort(expected_first + 1, expected_last - 1, compare);
+        else
+            std::sort(expected_first + 1, expected_last - 1, compare);
+        int32_t count0 = KeyCount;
+        if (Stable)
+            stable_sort(exec, tmp_first + 1, tmp_last - 1, compare);
+        else
+            sort(exec, tmp_first + 1, tmp_last - 1, compare);
+
+        for (size_t i = 0; i < n; ++i, ++expected_first, ++tmp_first)
+        {
+            // Check that expected[i] is equal to tmp[i]
+            EXPECT_TRUE(Equal(*expected_first, *tmp_first), "bad sort");
+        }
+        int32_t count1 = KeyCount;
+        EXPECT_EQ(count0, count1, "key cleanup error");
+    }
+    template <typename Policy, typename InputIterator, typename OutputIterator, typename OutputIterator2, typename Size,
+              typename Compare>
+    typename std::enable_if<!is_same_iterator_category<InputIterator, std::random_access_iterator_tag>::value,
+                            void>::type
+    operator()(Policy&& exec, OutputIterator tmp_first, OutputIterator tmp_last, OutputIterator2 expected_first,
+               OutputIterator2 expected_last, InputIterator first, InputIterator last, Size n, Compare compare)
+    {
+    }
+};
+
+template <typename T, typename Compare, typename Convert>
+void
+test_sort(Compare compare, Convert convert)
+{
+    for (size_t n = 0; n < 100000; n = n <= 16 ? n + 1 : size_t(3.1415 * n))
+    {
+        LastIndex = n + 2;
+        // The rand()%(2*n+1) encourages generation of some duplicates.
+        // Sequence is padded with an extra element at front and back, to detect overwrite bugs.
+        Sequence<T> in(n + 2, [=](size_t k) { return convert(k, rand() % (2 * n + 1)); });
+        Sequence<T> expected(in);
+        Sequence<T> tmp(in);
+        invoke_on_all_policies(test_sort_with_compare(), tmp.begin(), tmp.end(), expected.begin(), expected.end(),
+                               in.begin(), in.end(), in.size(), compare);
+    }
+}
+
+template <typename T>
+struct test_non_const
+{
+    template <typename Policy, typename Iterator>
+    void
+    operator()(Policy&& exec, Iterator iter)
+    {
+        sort(exec, iter, iter, non_const(std::less<T>()));
+        stable_sort(exec, iter, iter, non_const(std::less<T>()));
+    }
+};
+
+int32_t
+main()
+{
+    std::srand(42);
+    for (int32_t kind = 0; kind < 2; ++kind)
+    {
+        Stable = kind != 0;
+        test_sort<ParanoidKey>(KeyCompare(OddTag()),
+                               [](size_t k, size_t val) { return ParanoidKey(k, val, OddTag()); });
+        test_sort<float32_t>([](float32_t x, float32_t y) { return x < y; },
+                             [](size_t, size_t val) { return float32_t(val); });
+        test_sort<int32_t>(
+            [](int32_t x, int32_t y) { return x > y; }, // Reversed so accidental use of < will be detected.
+            [](size_t, size_t val) { return int32_t(val); });
+    }
+
+    test_algo_basic_single<int32_t>(run_for_rnd<test_non_const<int32_t>>());
+
+    std::cout << done() << std::endl;
+    return 0;
+}