What Sorting Algorithm Does Swift Implement For Its Standard Library

What sorting algorithm does Swift implement for its standard library?

Update 2: As we can see in Sort.swift, sort() now uses a “modified timsort” in Swift 5. Timsort is a

... hybrid stable sorting algorithm, derived from merge sort and insertion sort ...
In the worst case, Timsort takes O(n log n) comparisons to sort an array of n elements. In the best case, which occurs when the input is already sorted, it runs in linear time, meaning that it is an adaptive sorting algorithm.

This means that sort() happens to be a stable sort in Swift 5, but that is still an implementation detail. The MutableCollection.sort documentation states that

The sorting algorithm is not guaranteed to be stable. A stable sort preserves the relative order of elements that compare equal.

See also Is sort() stable in Swift 5? in the Swift forum:

The algorithm was only recently made stable in preparation for a proposal to make it guaranteed as such.

Update: Swift is open source now, and in

https://github.com/apple/swift/blob/master/stdlib/public/core/Sort.swift

one can see that sorting a collection is done using introsort
with a maximum recursion depth of 2*floor(log_2(N)). It switches to insertion sort for partitions with less than 20 elements, or to heapsort
if the recursion depth is reached.

Old answer: Defining a custom Comparable structure and setting in breakpoint in <:

struct MyStruct : Comparable {
    let val : Int
}

func ==(x: MyStruct, y: MyStruct) -> Bool {
    println("\(x.val) ==  \(y.val)")
    return x.val == y.val
}
func <(x: MyStruct, y: MyStruct) -> Bool {
    println("\(x.val) < \(y.val)")
    return x.val < y.val // <--- SET BREAKPOINT HERE
}

var array = [MyStruct]()
for _ in 1 ... 30 {
    array.append(MyStruct(val: Int(arc4random_uniform(1000))))
}
sort(&array)

shows the following stack backtrace:


(lldb) bt
* thread #1: tid = 0x5a00, 0x00000001001cb806 sort`sort. Swift.Bool + 454 at main.swift:22, queue = 'com.apple.main-thread', stop reason = breakpoint 1.1
  * frame #0: 0x00000001001cb806 sort`sort. Swift.Bool + 454 at main.swift:22
    frame #1: 0x00000001001cb62b sort`protocol witness for Swift._Comparable.(Swift._Comparable.Self.Type)(Swift._Comparable.Self, Swift._Comparable.Self) -> Swift.Bool in conformance sort.MyStruct : Swift._Comparable + 27 at main.swift:20
    frame #2: 0x00000001000f5a98 sort`Swift._partition (inout A, Swift.Range) -> A.Index + 3224
    frame #3: 0x00000001000f756a sort`Swift._introSortImpl (inout A, Swift.Range, Swift.Int) -> () + 2138
    frame #4: 0x00000001000f6c01 sort`Swift._introSort (inout A, Swift.Range) -> () + 1233
    frame #5: 0x00000001000fc47f sort`Swift.sort (inout A) -> () + 607
    frame #6: 0x000000010013ea77 sort`partial apply forwarder for Swift.(sort (inout Swift.Array) -> ()).(closure #1) + 183
    frame #7: 0x000000010013eaf8 sort`partial apply forwarder for reabstraction thunk helper  from @callee_owned (@inout Swift.UnsafeMutableBufferPointer) -> (@unowned ()) to @callee_owned (@inout Swift.UnsafeMutableBufferPointer) -> (@out ()) + 56
    frame #8: 0x0000000100046c4b sort`Swift.Array.withUnsafeMutableBufferPointer (inout Swift.Array)((inout Swift.UnsafeMutableBufferPointer) -> B) -> B + 475
    frame #9: 0x00000001000fc5ad sort`Swift.sort (inout Swift.Array) -> () + 157
    frame #10: 0x00000001001cb465 sort`top_level_code + 1237 at main.swift:29
    frame #11: 0x00000001001cbdca sort`main + 42 at main.swift:0
    frame #12: 0x00007fff8aa9a5fd libdyld.dylib`start + 1

and later

(lldb) bt
* thread #1: tid = 0x5a00, 0x00000001001cb806 sort`sort. Swift.Bool + 454 at main.swift:22, queue = 'com.apple.main-thread', stop reason = breakpoint 1.1
  * frame #0: 0x00000001001cb806 sort`sort. Swift.Bool + 454 at main.swift:22
    frame #1: 0x00000001001cb62b sort`protocol witness for Swift._Comparable.(Swift._Comparable.Self.Type)(Swift._Comparable.Self, Swift._Comparable.Self) -> Swift.Bool in conformance sort.MyStruct : Swift._Comparable + 27 at main.swift:20
    frame #2: 0x00000001000f449e sort`Swift._insertionSort (inout A, Swift.Range) -> () + 2958
    frame #3: 0x00000001000f730e sort`Swift._introSortImpl (inout A, Swift.Range, Swift.Int) -> () + 1534
    frame #4: 0x00000001000f797d sort`Swift._introSortImpl (inout A, Swift.Range, Swift.Int) -> () + 3181
    frame #5: 0x00000001000f6c01 sort`Swift._introSort (inout A, Swift.Range) -> () + 1233
    frame #6: 0x00000001000fc47f sort`Swift.sort (inout A) -> () + 607
    frame #7: 0x000000010013ea77 sort`partial apply forwarder for Swift.(sort (inout Swift.Array) -> ()).(closure #1) + 183
    frame #8: 0x000000010013eaf8 sort`partial apply forwarder for reabstraction thunk helper  from @callee_owned (@inout Swift.UnsafeMutableBufferPointer) -> (@unowned ()) to @callee_owned (@inout Swift.UnsafeMutableBufferPointer) -> (@out ()) + 56
    frame #9: 0x0000000100046c4b sort`Swift.Array.withUnsafeMutableBufferPointer (inout Swift.Array)((inout Swift.UnsafeMutableBufferPointer) -> B) -> B + 475
    frame #10: 0x00000001000fc5ad sort`Swift.sort (inout Swift.Array) -> () + 157
    frame #11: 0x00000001001cb465 sort`top_level_code + 1237 at main.swift:29
    frame #12: 0x00000001001cbdca sort`main + 42 at main.swift:0
    frame #13: 0x00007fff8aa9a5fd libdyld.dylib`start + 1

This confirms the conjecture of Airspeed's answer that introsort is used
in combination with insertion sort for the smaller ranges.

If the array has less than 20 elements then only insertion sort seems to be used.
This could indicate that the threshold for switching from introsort to
insertion sort is 20.

Of course the implementation might change in the future.

Which general purpose sorting algorithm does Swift use? It does not perform well on sorted data

Swift uses Introsort. Looking at the source code we see that the chosen pivot is the first element. The wikipedia page on Introsort says:

(...), one of the critical operations is choosing the pivot: the
element around which the list is partitioned. The simplest pivot
selection algorithm is to take the first or the last element of the
list as the pivot, causing poor behavior for the case of sorted or
nearly sorted input.

Thus it is entirely predictable, given the implementation choice, that Swift's sorting performance is worst for sorted inputs.

I have built a complete benchmark for people who want to easily reproduce the OP's claims :
https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/tree/master/extra/swift/sort

For reference, the GNU ISO C++ standard library uses a median-of-3 pivot (as per the stl_algo.h header).

How to stable sort an array in swift?

let sortedArray = (recipes as NSArray).sortedArray(options: .stable, usingComparator: { (lhs, rhs) -> ComparisonResult in
    let lhs = (lhs as! Recipe)
    let rhs = (rhs as! Recipe)
    if lhs.skill.value == rhs.skill.value {
        return ComparisonResult.orderedSame
    } else if lhs.skill.value < rhs.skill.value {
        return ComparisonResult.orderedAscending
    } else {
        return ComparisonResult.orderedDescending
    }
})

Took from here: https://medium.com/@cocotutch/a-swift-sorting-problem-e0ebfc4e46d4

Why isn't Swift's .sort( ) method able to guarantee stability if it's underlying algorithm are generally stable?

In short, they are still deciding whether the algorithm should be stable or not by default, or whether there should be two functions (stable and unstable).

So they did a simple thing - they made it stable before Swift 5.0 but without guaranteeing it to be stable. Whatever they decide, they can make it backward compatible (if they decide the sort won't be stable, it doesn't matter if it has been stable before. If they decide the sort will be stable, then only documentation change is required).

Which sorting algorithm does qsort() use?

The qsort() function may be implemented using any sort algorithm that the library implementer chooses, but the name suggests that the algorithm should be close to optimal. Using an O(N²) algorithm would be permissible, but a major QoI (quality of implementation) issue.

It is worth noting that comparison is quite expensive with the qsort() interface; any sort algorithm that increases the number of comparisons to reduce the number of moves (which can also be expensive if you are not shuffling pointers) may lead to worse performance. However, that's an issue for the library implementer to be concerned with. Unless you find that the library implementation is horrid (which is pretty unlikely these days), use it and don't worry.

The C++ sort algorithm can run rings around C's qsort.

What sorting algorithm is used by programmers?

I am currently studying algorithms at college and I am curios as what does a seasoned developer uses in its code when said programmer needs to sort something.

Different sorting algorithms have different applications. You choose the best algorithm for the problem you're facing. For example, if you have a list of items in-memory then you can sort them in-place with QuickSort - if you want to sort items that are streamed-in (i.e. an online sort) then QuickSort wouldn't be appropriate.

C++ uses IntroSort which has an average of Θ(n log(n)) and worst of Θ(n^2).

I think you mean C++'s STL sort defaults to using Introsort in most implementations (including the original SGI STL and GNU's, but I don't believe the C++ specification specifically requires sort to use Introsort - it only requires it to be a stable sort. C++ is just a language, which does not have a sorting-algorithm built in to the language. Anyway, it's a library feature, not a language feature.

C# uses QuickSort which has an average of Θ(n log(n)) and worst of Θ(n^2).

Again, C# (the language) does not have any built-in sorting functionality. It's a .NET BCL (Base Class Library) feature that exposes methods that perform the sorting (such as Array.Sort, List<T>.Sort, Enumerable.OrderBy<T>, and so on). Unlike the C++ specification, the C# official documentation does state that the algorithm used by List<T>.Sort is Quicksort, but other methods like Enumerable.OrderBy<T> leave the actual sorting algorithm used to the backend provider (e.g. in Linq-to-SQL and Linq-to-Entities the sorting is performed by the remote database engine).

Do programmers use the default sorting methods or they implement their own ?

Generally speaking, we use the defaults because they're good enough for 95%+ of all workloads and scenarios - or because the specification allows the toolchain and library we're using to pick the best algorithm for the runtime platform (e.g. C++'s sort could hypothetically make use of hardware-sorting which allows for sorting of constrained values of n in O(1) to O(n) worst-case time instead of O(n^2) with QuickSort - which is a problem when processing unsanitized user-input.

But also, generally speaking, programmers should never reimplement their own sorting algorithms. Modern languages with support for templates and generics mean that an algorithm can be written in the general form for us, so we just need to provide the data to be sorted and either comparator function or a sorting key selector, which avoids common programmer human errors when reimplementing a stock algorithm.

As for the possibility of programmers inventing their own new novel sorting algorithms... with few exceptions that really doesn't happen. As with cryptography, if you find yourself "inventing" a new sorting algorithm I guarantee that not only are you not inventing a new algorithm, but that your algorithm will be flawed in some way or another. In short: don't - at least not until you've ran your idea past your nearest computer science academic.

When do they use the default one and when do they implement their own ?

See above. You're also not considering using a non-default algorithm. As the other answers have said, it's based on the application, i.e. the problem you're trying to solve.

Is Θ(n log(n)) the best time a sorting algorithm can get ?

You need to understand the difference between Best-case, Average-case, and Worst-case time complexities. Just read the Wikipedia article section with the big table that shows you the different runtime complexities: https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_sorts - for example, insertion sort has a best-case time complexity of O(n) which is much better than O(n log n), which directly contradicts your supposition.

There are a ton of sorting algorithm, as I am currently finding out in uni.

I think you would be better served by bringing your questions to your class TA/prof/reader as they know the course material you're using and know the context in which you're asking.

How to implement classic sorting algorithms in modern C++?

Algorithmic building blocks

We begin by assembling the algorithmic building blocks from the Standard Library:

#include <algorithm>    // min_element, iter_swap, 
                        // upper_bound, rotate, 
                        // partition, 
                        // inplace_merge,
                        // make_heap, sort_heap, push_heap, pop_heap,
                        // is_heap, is_sorted
#include <cassert>      // assert 
#include <functional>   // less
#include <iterator>     // distance, begin, end, next

the iterator tools such as non-member std::begin() / std::end() as well as with std::next() are only available as of C++11 and beyond. For C++98, one needs to write these himself. There are substitutes from Boost.Range in boost::begin() / boost::end(), and from Boost.Utility in boost::next().
the std::is_sorted algorithm is only available for C++11 and beyond. For C++98, this can be implemented in terms of std::adjacent_find and a hand-written function object. Boost.Algorithm also provides a boost::algorithm::is_sorted as a substitute.
the std::is_heap algorithm is only available for C++11 and beyond.

Syntactical goodies

C++14 provides transparent comparators of the form std::less<> that act polymorphically on their arguments. This avoids having to provide an iterator's type. This can be used in combination with C++11's default function template arguments to create a single overload for sorting algorithms that take < as comparison and those that have a user-defined comparison function object.

template<class It, class Compare = std::less<>>
void xxx_sort(It first, It last, Compare cmp = Compare{});

In C++11, one can define a reusable template alias to extract an iterator's value type which adds minor clutter to the sort algorithms' signatures:

template<class It>
using value_type_t = typename std::iterator_traits<It>::value_type;

template<class It, class Compare = std::less<value_type_t<It>>>
void xxx_sort(It first, It last, Compare cmp = Compare{});

In C++98, one needs to write two overloads and use the verbose typename xxx<yyy>::type syntax

template<class It, class Compare>
void xxx_sort(It first, It last, Compare cmp); // general implementation

template<class It>
void xxx_sort(It first, It last)
{
    xxx_sort(first, last, std::less<typename std::iterator_traits<It>::value_type>());
}

Another syntactical nicety is that C++14 facilitates wrapping user-defined comparators through polymorphic lambdas (with auto parameters that are deduced like function template arguments).
C++11 only has monomorphic lambdas, that require the use of the above template alias value_type_t.
In C++98, one either needs to write a standalone function object or resort to the verbose std::bind1st / std::bind2nd / std::not1 type of syntax.
Boost.Bind improves this with boost::bind and _1 / _2 placeholder syntax.
C++11 and beyond also have std::find_if_not, whereas C++98 needs std::find_if with a std::not1 around a function object.

C++ Style

There is no generally acceptable C++14 style yet. For better or for worse, I closely follow Scott Meyers's draft Effective Modern C++ and Herb Sutter's revamped GotW. I use the following style recommendations:

Herb Sutter's "Almost Always Auto" and Scott Meyers's "Prefer auto to specific type declarations" recommendation, for which the brevity is unsurpassed, although its clarity is sometimes disputed.
Scott Meyers's "Distinguish () and {} when creating objects" and consistently choose braced-initialization {} instead of the good old parenthesized initialization () (in order to side-step all most-vexing-parse issues in generic code).
Scott Meyers's "Prefer alias declarations to typedefs". For templates this is a must anyway, and using it everywhere instead of typedef saves time and adds consistency.
I use a for (auto it = first; it != last; ++it) pattern in some places, in order to allow for loop invariant checking for already sorted sub-ranges. In production code, the use of while (first != last) and a ++first somewhere inside the loop might be slightly better.

Selection sort

Selection sort does not adapt to the data in any way, so its runtime is always O(N²). However, selection sort has the property of minimizing the number of swaps. In applications where the cost of swapping items is high, selection sort very well may be the algorithm of choice.

To implement it using the Standard Library, repeatedly use std::min_element to find the remaining minimum element, and iter_swap to swap it into place:

template<class FwdIt, class Compare = std::less<>>
void selection_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    for (auto it = first; it != last; ++it) {
        auto const selection = std::min_element(it, last, cmp);
        std::iter_swap(selection, it); 
        assert(std::is_sorted(first, std::next(it), cmp));
    }
}

Note that selection_sort has the already processed range [first, it) sorted as its loop invariant. The minimal requirements are forward iterators, compared to std::sort's random access iterators.

Details omitted:

selection sort can be optimized with an early test if (std::distance(first, last) <= 1) return; (or for forward / bidirectional iterators: if (first == last || std::next(first) == last) return;).
for bidirectional iterators, the above test can be combined with a loop over the interval [first, std::prev(last)), because the last element is guaranteed to be the minimal remaining element and doesn't require a swap.

Insertion sort

Although it is one of the elementary sorting algorithms with O(N²) worst-case time, insertion sort is the algorithm of choice either when the data is nearly sorted (because it is adaptive) or when the problem size is small (because it has low overhead). For these reasons, and because it is also stable, insertion sort is often used as the recursive base case (when the problem size is small) for higher overhead divide-and-conquer sorting algorithms, such as merge sort or quick sort.

To implement insertion_sort with the Standard Library, repeatedly use std::upper_bound to find the location where the current element needs to go, and use std::rotate to shift the remaining elements upward in the input range:

template<class FwdIt, class Compare = std::less<>>
void insertion_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    for (auto it = first; it != last; ++it) {
        auto const insertion = std::upper_bound(first, it, *it, cmp);
        std::rotate(insertion, it, std::next(it)); 
        assert(std::is_sorted(first, std::next(it), cmp));
    }
}

Note that insertion_sort has the already processed range [first, it) sorted as its loop invariant. Insertion sort also works with forward iterators.

Details omitted:

insertion sort can be optimized with an early test if (std::distance(first, last) <= 1) return; (or for forward / bidirectional iterators: if (first == last || std::next(first) == last) return;) and a loop over the interval [std::next(first), last), because the first element is guaranteed to be in place and doesn't require a rotate.
for bidirectional iterators, the binary search to find the insertion point can be replaced with a reverse linear search using the Standard Library's std::find_if_not algorithm.

Four Live Examples (C++14, C++11, C++98 and Boost, C++98) for the fragment below:

using RevIt = std::reverse_iterator<BiDirIt>;
auto const insertion = std::find_if_not(RevIt(it), RevIt(first), 
    [=](auto const& elem){ return cmp(*it, elem); }
).base();

For random inputs this gives O(N²) comparisons, but this improves to O(N) comparisons for almost sorted inputs. The binary search always uses O(N log N) comparisons.
For small input ranges, the better memory locality (cache, prefetching) of a linear search might also dominate a binary search (one should test this, of course).

Quick sort

When carefully implemented, quick sort is robust and has O(N log N) expected complexity, but with O(N²) worst-case complexity that can be triggered with adversarially chosen input data. When a stable sort is not needed, quick sort is an excellent general-purpose sort.

Even for the simplest versions, quick sort is quite a bit more complicated to implement using the Standard Library than the other classic sorting algorithms. The approach below uses a few iterator utilities to locate the middle element of the input range [first, last) as the pivot, then use two calls to std::partition (which are O(N)) to three-way partition the input range into segments of elements that are smaller than, equal to, and larger than the selected pivot, respectively. Finally the two outer segments with elements smaller than and larger than the pivot are recursively sorted:

template<class FwdIt, class Compare = std::less<>>
void quick_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    auto const N = std::distance(first, last);
    if (N <= 1) return;
    auto const pivot = *std::next(first, N / 2);
    auto const middle1 = std::partition(first, last, [=](auto const& elem){ 
        return cmp(elem, pivot); 
    });
    auto const middle2 = std::partition(middle1, last, [=](auto const& elem){ 
        return !cmp(pivot, elem);
    });
    quick_sort(first, middle1, cmp); // assert(std::is_sorted(first, middle1, cmp));
    quick_sort(middle2, last, cmp);  // assert(std::is_sorted(middle2, last, cmp));
}

However, quick sort is rather tricky to get correct and efficient, as each of the above steps has to be carefully checked and optimized for production level code. In particular, for O(N log N) complexity, the pivot has to result into a balanced partition of the input data, which cannot be guaranteed in general for an O(1) pivot, but which can be guaranteed if one sets the pivot as the O(N) median of the input range.

Details omitted:

the above implementation is particularly vulnerable to special inputs, e.g. it has O(N^2) complexity for the "organ pipe" input 1, 2, 3, ..., N/2, ... 3, 2, 1 (because the middle is always larger than all other elements).
median-of-3 pivot selection from randomly chosen elements from the input range guards against almost sorted inputs for which the complexity would otherwise deteriorate to O(N^2).
3-way partitioning (separating elements smaller than, equal to and larger than the pivot) as shown by the two calls to std::partition is not the most efficient O(N) algorithm to achieve this result.
for random access iterators, a guaranteed O(N log N) complexity can be achieved through median pivot selection using std::nth_element(first, middle, last), followed by recursive calls to quick_sort(first, middle, cmp) and quick_sort(middle, last, cmp).
this guarantee comes at a cost, however, because the constant factor of the O(N) complexity of std::nth_element can be more expensive than that of the O(1) complexity of a median-of-3 pivot followed by an O(N) call to std::partition (which is a cache-friendly single forward pass over the data).

Merge sort

If using O(N) extra space is of no concern, then merge sort is an excellent choice: it is the only stable O(N log N) sorting algorithm.

It is simple to implement using Standard algorithms: use a few iterator utilities to locate the middle of the input range [first, last) and combine two recursively sorted segments with a std::inplace_merge:

template<class BiDirIt, class Compare = std::less<>>
void merge_sort(BiDirIt first, BiDirIt last, Compare cmp = Compare{})
{
    auto const N = std::distance(first, last);
    if (N <= 1) return;                   
    auto const middle = std::next(first, N / 2);
    merge_sort(first, middle, cmp); // assert(std::is_sorted(first, middle, cmp));
    merge_sort(middle, last, cmp);  // assert(std::is_sorted(middle, last, cmp));
    std::inplace_merge(first, middle, last, cmp); // assert(std::is_sorted(first, last, cmp));
}

Merge sort requires bidirectional iterators, the bottleneck being the std::inplace_merge. Note that when sorting linked lists, merge sort requires only O(log N) extra space (for recursion). The latter algorithm is implemented by std::list<T>::sort in the Standard Library.

Heap sort

Heap sort is simple to implement, performs an O(N log N) in-place sort, but is not stable.

The first loop, O(N) "heapify" phase, puts the array into heap order. The second loop, the O(N log N) "sortdown" phase, repeatedly extracts the maximum and restores heap order. The Standard Library makes this extremely straightforward:

template<class RandomIt, class Compare = std::less<>>
void heap_sort(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
    lib::make_heap(first, last, cmp); // assert(std::is_heap(first, last, cmp));
    lib::sort_heap(first, last, cmp); // assert(std::is_sorted(first, last, cmp));
}

In case you consider it "cheating" to use std::make_heap and std::sort_heap, you can go one level deeper and write those functions yourself in terms of std::push_heap and std::pop_heap, respectively:

namespace lib {

// NOTE: is O(N log N), not O(N) as std::make_heap
template<class RandomIt, class Compare = std::less<>>
void make_heap(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
    for (auto it = first; it != last;) {
        std::push_heap(first, ++it, cmp); 
        assert(std::is_heap(first, it, cmp));           
    }
}

template<class RandomIt, class Compare = std::less<>>
void sort_heap(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
    for (auto it = last; it != first;) {
        std::pop_heap(first, it--, cmp);
        assert(std::is_heap(first, it, cmp));           
    } 
}

}   // namespace lib

The Standard Library specifies both push_heap and pop_heap as complexity O(log N). Note however that the outer loop over the range [first, last) results in O(N log N) complexity for make_heap, whereas std::make_heap has only O(N) complexity. For the overall O(N log N) complexity of heap_sort it doesn't matter.

Details omitted: O(N) implementation of make_heap

Testing

Here are four Live Examples (C++14, C++11, C++98 and Boost, C++98) testing all five algorithms on a variety of inputs (not meant to be exhaustive or rigorous). Just note the huge differences in the LOC: C++11/C++14 need around 130 LOC, C++98 and Boost 190 (+50%) and C++98 more than 270 (+100%).

What sorting algorithm does visual c++ use in std::sort

Use the source Luke :) its quicksort (MSVC 2013) or some times heap sort or even insertion sort (based on the size of the container)

template<class _RanIt,
    class _Diff> inline
    void _Sort(_RanIt _First, _RanIt _Last, _Diff _Ideal)
    {   // order [_First, _Last), using operator<
    _Diff _Count;
    for (; _ISORT_MAX < (_Count = _Last - _First) && 0 < _Ideal; )
        {   // divide and conquer by quicksort

What Sorting Algorithm Does Swift Implement For Its Standard Library