diff --git a/pstl/include/pstl/internal/parallel_backend_omp.h b/pstl/include/pstl/internal/parallel_backend_omp.h
--- a/pstl/include/pstl/internal/parallel_backend_omp.h
+++ b/pstl/include/pstl/internal/parallel_backend_omp.h
@@ -548,113 +548,95 @@
 // parallel_stable_sort
 //------------------------------------------------------------------------
 
-template <typename _RandomAccessIterator>
-struct _MinKItems
-{
+template <typename _RandomAccessIterator> struct _MinKItems {
     using _MinKVector = std::vector<_RandomAccessIterator>;
     _MinKVector __smallest_k_items;
-    typename _MinKVector::iterator __largest_item;
+    std::size_t __largest_item;
 
-    bool
-    __empty()
-    {
-        return __smallest_k_items.empty();
-    }
+    bool __empty() { return __smallest_k_items.empty(); }
 
-    auto
-    __size()
-    {
-        return std::size(__smallest_k_items);
-    }
+    auto __size() { return std::size(__smallest_k_items); }
 
-    void
-    __resize(std::size_t new_size)
-    {
-        __smallest_k_items.resize(new_size);
+    void __resize(std::size_t new_size) { __smallest_k_items.resize(new_size); }
+
+    auto __get_largest_item() { return __smallest_k_items[__largest_item]; }
+
+    auto __set_largest_item(_RandomAccessIterator it) {
+        __smallest_k_items[__largest_item] = it;
     }
 };
 
-template <typename _RandomAccessIterator, typename _Compare>
-struct _MinKOp
-{
-    _MinKItems<_RandomAccessIterator>& __items;
+template <typename _RandomAccessIterator, typename _Compare> struct _MinKOp {
+    _MinKItems<_RandomAccessIterator> &__items;
     _Compare __comp;
 
-    _MinKOp(_MinKItems<_RandomAccessIterator>& __items_, _Compare __comp_) : __items(__items_), __comp(__comp_) {}
+    _MinKOp(_MinKItems<_RandomAccessIterator> &__items_, _Compare __comp_)
+        : __items(__items_), __comp(__comp_) {}
 
-    void
-    __keep_smallest_k_items(_RandomAccessIterator __item)
-    {
+    void __keep_smallest_k_items(_RandomAccessIterator __item) {
         // If the new item is larger than the largest item in the list, discard it.
-        if (__comp(**__items.__largest_item, *__item))
-        {
+        if (__comp(*__items.__get_largest_item(), *__item)) {
             return;
         }
 
         // If thew new item is equal to the largest item in the list, discard it.
-        if (!__comp(*__item, **__items.__largest_item))
-        {
+        if (!__comp(*__item, *__items.__get_largest_item())) {
             return;
         }
 
         // The new item is smaller than the largest item. Replace the largest item
         // with the new item.
-        *__items.__largest_item = __item;
+        __items.__set_largest_item(__item);
 
         // Find the new largest item.
         __update_largest_item();
     };
 
-    void
-    __update_largest_item()
-    {
+    void __update_largest_item() {
+        auto pos = std::max_element(
+            std::begin(__items.__smallest_k_items),
+            std::end(__items.__smallest_k_items),
+            [this](const auto &l, const auto &r) { return __comp(*l, *r); });
         __items.__largest_item =
-            std::max_element(std::begin(__items.__smallest_k_items), std::end(__items.__smallest_k_items),
-                             [this](const auto& l, const auto& r) { return __comp(*l, *r); });
+            std::distance(std::begin(__items.__smallest_k_items), pos);
     }
 
-    void
-    __merge(_MinKItems<_RandomAccessIterator>& __other)
-    {
-        for (auto __it = std::begin(__other.__smallest_k_items); __it != std::end(__other.__smallest_k_items); ++__it)
-        {
+    void __merge(_MinKItems<_RandomAccessIterator> &__other) {
+        for (auto __it = std::begin(__other.__smallest_k_items);
+             __it != std::end(__other.__smallest_k_items); ++__it) {
             __keep_smallest_k_items(*__it);
         }
+        __update_largest_item();
     }
 
-    void
-    __initialize(_RandomAccessIterator __first, _RandomAccessIterator __last, std::size_t __k)
-    {
+    void __initialize(_RandomAccessIterator __first, _RandomAccessIterator __last,
+                      std::size_t __k) {
         __items.__resize(__k);
         auto __item_it = __first;
         for (auto __tracking_it = begin(__items.__smallest_k_items);
-             __item_it != __last && __tracking_it != end(__items.__smallest_k_items); ++__item_it, ++__tracking_it)
-        {
+             __item_it != __last &&
+             __tracking_it != end(__items.__smallest_k_items);
+             ++__item_it, ++__tracking_it) {
             *__tracking_it = __item_it;
         }
         __update_largest_item();
-        for (; __item_it != __last; ++__item_it)
-        {
+        for (; __item_it != __last; ++__item_it) {
             __keep_smallest_k_items(__item_it);
         }
     }
 
-    static auto
-    __reduce(_MinKItems<_RandomAccessIterator>& __v1, _MinKItems<_RandomAccessIterator>& __v2, _Compare __comp)
-        -> _MinKItems<_RandomAccessIterator>
-    {
-        if (__v1.__empty())
-        {
+    static auto __reduce(_MinKItems<_RandomAccessIterator> &__v1,
+                         _MinKItems<_RandomAccessIterator> &__v2, _Compare __comp)
+    -> _MinKItems<_RandomAccessIterator> {
+        if (__v1.__empty()) {
             return __v2;
         }
 
-        if (__v2.__empty())
-        {
+        if (__v2.__empty()) {
             return __v1;
         }
 
-        if (__v1.__size() >= __v2.__size())
-        {
+        if (__v1.__size() >= __v2.__size()) {
             _MinKOp<_RandomAccessIterator, _Compare> __op(__v1, __comp);
             __op.__merge(__v2);
             return __v1;
@@ -720,7 +702,7 @@
     auto __reduce_value = [&](auto& __v1, auto& __v2) { return _Op::__reduce(__v1, __v2, __comp); };
     auto __result = __parallel_reduce_chunks<_Value>(0, __n_chunks, __reduce_chunk, __reduce_value);
 
-    return *__result.__largest_item;
+    return __result.__get_largest_item();
 }
 
 template <typename _RandomAccessIterator, typename _Compare>
@@ -775,7 +757,7 @@
             {
                 auto __current_item = std::next(__xs, __index);
                 auto __swap_item = std::next(__xs, __swap_index);
-                std::swap(__current_item, __swap_item);
+                std::swap(*__current_item, *__swap_item);
                 break;
             }
         }
@@ -866,30 +848,32 @@
 {
     auto __pivot = __parallel_find_pivot(__xs, __xe, __comp, __nsort);
     __parallel_partition(__xs, __xe, __pivot, __comp, __nsort);
+    auto __part_end = std::next(__xs, __nsort);
 
     if (__nsort <= __default_chunk_size)
     {
-        __leaf_sort(__xs, __pivot, __comp);
+        __leaf_sort(__xs, __part_end, __comp);
     }
     else
     {
-        __parallel_stable_sort_body(__xs, __pivot, __comp);
+        __parallel_stable_sort_body(__xs, __part_end, __comp);
     }
 }
 
 template <class _ExecutionPolicy, typename _RandomAccessIterator, typename _Compare, typename _LeafSort>
 void
-__parallel_stable_sort(_ExecutionPolicy&&, _RandomAccessIterator __xs, _RandomAccessIterator __xe, _Compare __comp,
-                       _LeafSort __leaf_sort, std::size_t __nsort = 0)
+__parallel_stable_sort(_ExecutionPolicy&& __exec, _RandomAccessIterator __xs, _RandomAccessIterator __xe,
+                       _Compare __comp, _LeafSort __leaf_sort, std::size_t __nsort = 0)
 {
     if (__xs >= __xe)
     {
         return;
     }
 
-    if (__nsort < __default_chunk_size)
+    if (__nsort <= __default_chunk_size)
     {
-        __leaf_sort(__xs, __xe, __comp);
+        __serial_backend::__parallel_stable_sort(std::forward<_ExecutionPolicy>(__exec), __xs, __xe, __comp,
+                                                 __leaf_sort, __nsort);
         return;
     }