Tutorials
Books
Videos
Forums
Table of Contents
There are some activities our computer performs that are so common, we just don’t even bother talking about. Sorting is one such activity. Below is an example of me sorting some search results by name:
Now, here is the thing. There are very few cases where developers like you and me have to implement a sorting algorithm from scratch. The built-in sorting algorithms that programming languages provide is more than enough.
Do you know what sorting algorithms our favorite programming languages use for their built-in sort methods? The following list gives you the inside scoop:
JavaScript: JS uses a combination of quicksort and insertion sort in Chrome’s V8 engine. The ECMAScript standard doesn’t provide an official directive, so other JS engines may use other algorithms.
Python: Python's built-in sort capabilities use a variant of the Timsort algorithm
Java: In Java, the default sorts use Timsort for objects and a variant of quicksort for primitive values.
C++ Standard Library: The C++ Standard Library's uses an implementation of the introsort algorithm, which is a hybrid sorting algorithm combining quicksort, heapsort, and insertion sort.
C#: Similar to C++'s above, introsort is used.
Ruby: Ruby’s default sort methods use quicksort.
Swift: In Swift, sorting a collection uses the introsort algorithm, a common one we’ve seen so far!
PHP: PHP's sort() function keeps thing classy by using quicksort
Rust: Rust uses an adaptive sorting algorithm based on Timsort, but it is modified to handle more special cases
Go: The Go programming language uses pdqsort, an adaptive sorting algorithm based on a combination of quicksort, heapsort, and insertion sort.
What we see is that almost all default sort implementations use a hybrid algorithm like Timsort, introsort, or pdqsort to reduce the chance of worst-case scenarios. For example, we know that quicksort is really fast. We also know that quicksort has a worst-case running time of n-squared:
| Name | Best | Average | Worst | Memory |
|---|---|---|---|---|
| Quicksort | n log n | n log n | n2 | log n (average) |
| Mergesort | n log n | n log n | n log n | n (worst case) |
| Heapsort | n log n | n log n | n log n | 1 |
| Timsort | n | n log n | n log n | n |
| Bubble sort | n | n2 | n2 | 1 |
| Selection sort | n2 | n2 | n2 | 1 |
| Insertion sort | n | n2 | n2 | 1 |
The hybrid algorithms are good at detecting when a worst-case scenario may occur and adapt to using a different sorting approach at the right moment.
Even though almost all popular programming languages provide their own sorting algorithms, this doesn't mean we should forget everything we've learned so far. Just be aware that knowing how something works deeply has many additional benefits beyond reimplementing that same something from scratch. At least, that's what I tell myself! 😅
Just a final word before we wrap up. If you have a question and/or want to be part of a friendly, collaborative community of over 220k other developers like yourself, post on the forums for a quick response!
:: Copyright KIRUPA 2024 //--
