The KIRUPA orange logo! A stylized orange made to look like a glass of orange juice! Tutorials Books Videos Forums

Customize Theme


Color

Background


Done

Meet the Default Sorting Algorithms!

by kirupa   |   filed under Data Structures and Algorithms

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:

  1. 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.

  2. Python: Python's built-in sort capabilities use a variant of the Timsort algorithm

  3. Java: In Java, the default sorts use Timsort for objects and a variant of quicksort for primitive values.

  4. C++ Standard Library: The C++ Standard Library's uses an implementation of the introsort algorithm, which is a hybrid sorting algorithm combining quicksortheapsort, and insertion sort.

  5. C#: Similar to C++'s above, introsort is used.

  6. Ruby: Ruby’s default sort methods use quicksort.

  7. Swift: In Swift, sorting a collection uses the introsort algorithm, a common one we’ve seen so far!

  8. PHP: PHP's sort() function keeps thing classy by using quicksort

  9. Rust: Rust uses an adaptive sorting algorithm based on Timsort, but it is modified to handle more special cases

  10. Go: The Go programming language uses pdqsort, an adaptive sorting algorithm based on a combination of quicksortheapsort, 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.

Conclusion

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!

Kirupa's signature!

The KIRUPA Newsletter

Thought provoking content that lives at the intersection of design 🎨, development 🤖, and business 💰 - delivered weekly to over a bazillion subscribers!

SUBSCRIBE NOW

Serving you freshly baked content since 1998!
Killer icons by Dark Project Studios

Twitter Youtube Facebook Pinterest Instagram Github