1
$\begingroup$

In my algorithm class my teacher said that we should always use counting sort when we want to sort integers. After he said this I was curious to know in which situations I should choose one sort algorithm over another.

Looking at the complexities of the worst cases of the algorithms I know (heapsort, mergesort, quicksort and countingsort), excentuating the case where I want to sort integers, I will choose mergesort when I want a stable sorting algorithm or I will choose heapsort when I want to save memory.

Searching a little I found flashsort, but I still do not understand very well when I should implement it instead of others. Since I am beginning to study algorithms, I would like to know at this initial moment when a sort algorithm is preferable over others.

$\endgroup$
  • $\begingroup$ Suppose you want to sort a list of people by their birth day (365 different values). Then this can be done in $O(n)$ time with radix sort. $\endgroup$ – Pål GD Sep 10 '17 at 14:16
  • $\begingroup$ If a list is perfectly reversed, then quicksort might take $O(n^2)$ whereas merge sort takes $O(n \log n)$, however, "timsort" would probably be $O(n)$. $\endgroup$ – Pål GD Sep 10 '17 at 14:17
4
$\begingroup$

Most programming language standard libraries come equipped with one or more built-in sort routines these days. Most of the time, that's what you want.

"Library sort" algorithms tend to use a combination of basic sort algorithms that you've seen in class, and tune themselves either at compile time or at run time.

That's why, for example, the standard library sort in C++ might use merge sort on linked lists and quick sort on arrays. And a typical industrial-strength quick sort implementation will revert to insertion sort on small intervals, or heap sort if the partitioning strategy seems to be going awry.

Most library sorts are comparison-based because of external constraints. They must work on user-defined data types, for example, and it's typically much easier for the user of such a sort algorithm to supply a comparison operation than, say, a radix extraction operation. Moreover, users often want to sort on secondary keys if primary keys are equal (e.g. surname then first name). It's much easier to express this in terms of comparison rather than some other formulation.

I've been in the business a long time, and there's really only a few times I can think of where writing my own sort was the best option. Two examples that are easy to explain:

First example: I wrote the sort subsystem for a database server. It me about six months. As with library sorts, it used a combination of sort algorithms and adjusted its behaviour depending on what situation it found itself in. Sorting database records is an interesting case because accessing the sort key is sometimes the most expensive operation; disk seeks are one of the most expensive things there is, especially if the disk is network-attached.

The main idea which cracked this problem was to use the fact that users almost always wanted to sort on multiple keys. So I used partitioning sort algorithms which discovered "ranges" where the primary sort key was the same. Secondary keys are only needed to resolve those ranges. Many sort algorithms (e.g. ternary quick sort, radix sort) can be adapted to return ranges.

Second example: I wrote some firmware which needed to read about 1000 values from a hardware device, and then do quantile extraction. The complication is that the microcontroller that this ran on had essentially no extra read-write memory available, so algorithms like radix sort or quick sort were not an option. I used Shell sort, which was by far the best tradeoff.

There's a bunch of special-case information that everyone who has worked with sorting knows, such as "bubble sort is always worse than insertion sort", and "heap sort has terrible constant factors; last resort only". But this general advice is probably all you need to know:

  1. The best sort algorithm is the one that fits the peculiarities of your data and your platform.
  2. The second-best sort algorithm is one you didn't have to write.
  3. Make sure that sort is a bottleneck before getting fancy.

Knowing lots of sort algorithms is good for you, but not necessarily to the point where you can implement them from memory. Knowing that there is a tradeoff is more valuable knowledge than what the tradeoffs actually are. Then, when you come across one of those few times where you need to write your own sort, you'll know where to look.

$\endgroup$
0
$\begingroup$

Your question "when a sort algorithm is preferable over others." is somewhat broad, and maybe opinion-based. You could answer this question by reading about each sort algorithm. Usually textbooks (or articles such as on Wikipedia) discuss when and in which situations a certain algorithm more preferable over others.

Nevertheless, counting sort algorithm, unlike comparison based ones (such as Quick Sort or Merge Sort) runs in linear time, but at some cost. The keys are assumed to be non-negative integers. Time complexity of this algorithm is $O(a_{max} - a_{min})$ and so this algorithm is suitable only when $a_{max} - a_{min} \approx N $, where $N$ is the number keys. This article provides more detailed information. And this discusses the flash sort algorithm.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy