When Would You Implement Your Own Sorting Algorithm?

Question

Forgive me if this is a silly question....but I think back to my Comp. Sci. classes and I distinctly remember learning/being quizzed on several sorting algorithms and the corresponding 'Big O' notation.

Outside of the classroom though, I've never actually written code to sort.

When I get results from a database, I use 'Order By'. Otherwise, I use a collection class that implements a sort. I have implemented IComparable to allow sorting; but I've never gone beyond that.

Was sorting always just an academic pursuit for those of us who don't implement languages/frameworks? Or is it just that modern languages running on modern hardware make it a trivial detail to worry about?

Finally, when I call .Sort on a List(Of String), for example, what sort algorithm is being used under the hood?

There is almost never a need to implement your own sort routine, unless you're working in a low-level language with no 3rd-party libraries to hand. — Oliver Charlesworth, Apr 29 '11 at 22:34

score 4 · Accepted Answer · answered Apr 29 '11 at 22:34

While you rarely might need to implement a sorting algorithm yourself understanding the different algorithms and their complexity might help you in solving more complex problems.

Finally, when I call .Sort on a List(Of String), for example, what sort algorithm is being used under the hood?

Quick Sort

score 3 · Answer 2 · answered Apr 29 '11 at 22:36

I've never implemented my own sorting algorithm once since I took my CS classes in college and if I was ever even contemplating writing my own, I'd want my head examined first.

List<T> uses Quicksort per the MSDN documentation:

http://msdn.microsoft.com/en-us/library/b0zbh7b6.aspx

score 2 · Answer 3 · answered Apr 29 '11 at 22:40

You probably won't implement you own sorting algorithm if you are using high level languages...

What you have learnt in classroom was merely there to teach you of the existence and importance of the big O (omicron) notation.

It was there to make you know that optimization is always a goal in programming and that when you code something you must always think of how will it execute.

It teaches you that loops inside loops and recursions can lead to big performance problems if not analyzed/optimized well before coding starts.

It is a guidance to check your design before and be able to approximate the execution speed.

score 2 · Answer 4 · answered Apr 29 '11 at 22:44

It is important for a programmer to know how theses algorithms work. One reason would be that, in certain conditions, certain algorithms are better, although, sorting is rarely the bottleneck.

In some frameworks, the .Sort function uses various methods, depending on the situation.

score 1 · Answer 5 · answered Apr 29 '11 at 22:35

1

Modern languages running on modern hardware make it a trivial detail to worry about, unless a profiler shows that sorting is the bottleneck of your code.
According to this, List.Sort uses Array.Sort, which uses QuickSort.

answered Apr 29 '11 at 22:35

mellamokb

56,094
12
110
136

score 1 · Answer 6 · answered Apr 29 '11 at 22:35

IMO, it's become a bit of an academic exercise. You need to understand algorithmic complexity, and sorting is a good example for working through it because you can easily see the results and calculate the different complexities. In real life, though, there's almost certainly a library call that sorts your range faster than you would be able to do if you try to roll your own.

I don't know what the .Net libraries use for their defualt implementation, but I'd guess it's Quicksort or Shellsort. I'd be interested to find out if it's something else.

score 1 · Answer 7 · answered Apr 29 '11 at 22:37

I've occasionally had to write my own sort methods, but only when I was writing for a relatively immature and underpowered platform (like .Net 1.1 in Windows CE or embedded java or somesuch).

On anything resembling a modern computer, the best sorting algorithm is the ORDER BY clause in T-SQL.

score 1 · Answer 8 · answered Apr 29 '11 at 22:37

Implementing your own sort is the kind of thing that you do to gain insight in how algorithms work, what the tradeoffs are, which tried-and-true approaches that solve a wide array of problems efficiently are known, etc.

As Darin Dimitrov's answer states, library sort routines need to have a very competitive average-case performance, so quicksort is typically chosen.

score 1 · Answer 9 · edited May 23 '17 at 11:45

Was sorting always just an academic pursuit for those of us who don't implement languages/frameworks? Or is it just that modern languages running on modern hardware make it a trivial detail to worry about?

Even if you're not implementing your own routine, you may know how your data is likely to be arranged, and may want to choose a suitable library algorithm. For example, see this discussion on nearly sorted data.

score -2 · Answer 10 · answered Jun 21 '13 at 17:37

I think there are times when you need to have a custom sorting method. What if you wanted to sort by the make of cars, but not alphabetically? For example, you have a database with the makes: Honda, Lexus, Toyota, Acura, Nissan, Infiniti

If you use a plain sort, you get the order: Acura, Ford, Honda, Hyundai, Lexus, Toyota

What if you wanted to sort them based on a car company's standard and luxury class together? Lexus, Toyota, Honda, Acura, Nissan, Infiniti.

I think you would need a custom sort method if that's the case.

Nope, you would not. You would need to write a custom comparer (or use a sorting algorithm that accepts a projection for the item to sort on, such as the LINQ `OrderBy` method), but the sorting algorithm itself would be identical. — Servy, Jun 21 '13 at 17:40

When Would You Implement Your Own Sorting Algorithm?

10 Answers10