Sorting algorithms

danielbmartin · 03-16-2018, 12:16 PM

This question is prompted by curiosity, nothing more.

A Google search on sorting algorithm leads to this page (among others):
https://en.wikipedia.org/wiki/Sorting_algorithm

When a Linux programmer invokes the sort command, which algorithm is used? Are there "under the covers" several sorting programs and the sort command chooses the best for each case based on characteristics such as file size and line length?

Daniel B. Martin

dugan · 03-16-2018, 12:26 PM

Well, here's the source code for it:

https://github.com/coreutils/coreuti...ter/src/sort.c

Merge sort. According to Wikipedia.

rtmistler · 03-16-2018, 12:32 PM

The two places to research this should be:

Search for the word "algorithm" within the source, there are two occurrences I can see, one of which discusses Knuth, which memory serves would be the shell sort, or a modified shell, I forget. The other occurrence appears to be a btree using sequential sort.

Turbocapitalist · 03-16-2018, 12:42 PM

The OpenBSD sort has merge sort, quick sort, and radix sort.

https://cvsweb.openbsd.org/cgi-bin/c.../usr.bin/sort/

The code is quite clean so it should be feasible to port it if needed.

However, you'd have to use a runtime switch to tell it to use a different sort than merge sort which it also has for its default.

sundialsvcs · 03-16-2018, 09:34 PM

The sort-command is actually quite sophisticated, although it's not the best there is. Dr. Knuth wrote an entire book on "Sorting & Searching," if you are theoretical-mathematician enough to understand a single page of it.