DEV Community

Cover image for # Sorting Algorithms

# Sorting Algorithms

Edwin on November 21, 2020

If you google sorting Google will tell you that sorting is any process of arranging items systematically either in descending or ascending order. s...
Collapse
 
cubiclesocial profile image
cubiclesocial

Years ago I wrote a hybrid sorting algorithm that combined Quick, Heap, Shell, and Insertion sorts. Combining algorithms allowed resulted in outperforming the C++ std::sort routine implementation by over 25% across multiple compilers, platforms, and architectures (up to 40% gains in some cases) - a fairly impressive feat given that std::sort was already magnitudes faster than the old C library standby qsort() function. My general-purpose hybrid algorithm demonstrated that even Quicksort/Quicksort3 presents opportunities for major performance gains by combining multiple algorithms.

Basically, it boils down to big-O. Each sorting algorithm has strengths and weaknesses. Some are better at locality while others are better as broad strokes. For example, Quicksort doesn't work well at locality and/or if the data is in reverse order but works well enough otherwise while Insertion sort is generally terrible for almost everything except for small numbers of items (~3-5) where it dramatically outperforms all other sorting algorithms. It you break the problem into "sort large swaths of data but eventually sort smaller amounts of data" then it makes sense that no single algorithm is suitable for all situations and a hybrid approach that plays to each algorithm's strengths is going to have better overall performance metrics.

In fact, some standard C/C++ library authors understand this and dynamically switch between Quick and a Heap or Mergesort if they detect certain conditions that turn a Quicksort into no better than Bubblesort.