Meet the Default Sorting Algorithms! 👋
Meet the default sorting algorithms used by popular programming languages!
Hi everybody - 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
sortcapabilities 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:
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.
To learn more about common sorting algorithms, check out my Data Structures and Algorithms tutorials.
Till Next Time
Geeking out on sorting algorithms is one of my many hobbies, and I am almost done with my long-announced book on Data Structures and Algorithms. I will share more about the book once it gets closer to hitting bookstores. Until then, I’ll continue to share some little tidbits of interesting algorithm things I find.
If you want to reach out to me, reply to this newsletter, ping me on Twitter, or go to the forums like the good old days.
Cheers,
Kirupa 😁