# What is the easiest non-quadratic sorting algorithm? [closed]

If you had to teach one sorting algorithm that is faster than O(n²), which one would you pick?

It should be relatively easy to understand and implement, and it should require little theoretical background.

-
Why rule out O(n^2) That leaves out bubble sort (that's not only easy to explain but easy to implement). –  Loki Astari Jan 14 '11 at 1:32
@Martin: Because I don't find O(n²) algorithms particularly interesting to talk about. –  FredOverflow Jan 14 '11 at 1:34
I always found merge sort the easiest to comprehend, particularly when you are allowed to create new arrays on the fly and not worry about memory consumption that much. –  Job Jan 14 '11 at 1:43
"I wouldn't go w/ the bubble sort" - President Obama –  eggie5 Mar 17 '11 at 4:58
"Twas bubblesort, and slithy toves did gyre and gimble in the wabe" - Lewis Carroll –  Stephen C Mar 17 '11 at 5:16
show 1 more comment

## closed as primarily opinion-based by gnat, MichaelT, Kilian Foth, Bart van Ingen Schenau, GlenH7Jul 31 at 12:22

Many good questions generate some degree of opinion based on expert experience, but answers to this question will tend to be almost entirely based on opinions, rather than facts, references, or specific expertise.If this question can be reworded to fit the rules in the help center, please edit the question.

Quicksort lends itself pretty well to diagrams, and is relatively straightforward to implement if your students are comfortable with recursion and you don't insist on an in-place version.

-
Quicksort is worst case quadratic. And if you're doing a simplified version then, first, it's arguably not quicksort at all (the original ACM article specifically described the in-place version, and doing it in-place is one of the major reasons that it's fast in practice), and second you probably won't be doing the kind of randomised pivot selection that avoids the worst case behaviour. –  John Bartholomew Jan 14 '11 at 2:20
@John: This isn't about getting an efficient, production-quality, fast-in-practice sorting implementation. It's about understanding the algorithm involved. This arguably makes quicksort even better from an educational perspective, because it leads naturally into further discussion on its downsides and possible ways to remedy that. –  Anon. Jan 14 '11 at 2:28
As long as those details are addressed, then great, I'm all for it. But if you're aiming for "easiest" and "faster than quadratic", I'm not convinced that quicksort is it. Obviously that's subjective though, so that's for FredOverflow to decide in his particular case. –  John Bartholomew Jan 14 '11 at 2:36
@John Bartholomew: The fact that quick sort is "quadratic" is not subjective. Any naive implementation of quick sort will easily degrade to quadratic so you definitely have a point. –  Giorgio Jul 31 at 5:51

I'd teach Counting Sort (O(n)). It's great to start with because it's really simple -- you're just counting -- and yet it provides a bright student with two insights:

1. Sorting can be done in linear time
2. You don't need to actually compare elements in order to sort them

Then of course they might also start thinking about what happens when you don't know the range of the data, and if it interests them they can get into the more theoretical side.

-
Definitely worth pointing this out. It's easy to forget that the `O(n log n)` bound on sorting only applies to comparison based sorts. –  John Bartholomew Jan 14 '11 at 2:30
Counting sort is just a special case of radix sort. I'd want to introduce them together. I used to work on vector computers, and non-inplace quick sort, followed up by even/odd parallel bubble sort always worked great. Merge sort was also easy to understand, and useful if you need to put your data in external storage. In place quicksort is messy (and not stable). –  Omega Centauri Jan 14 '11 at 2:40
@Omega Radix sort is slightly harder to wrap your head around. It would be a great follow-up though. –  Matthew Read Jan 14 '11 at 2:45

To some extent it depends on the language (higher level languages make it easier to deal with algorithms that have to copy arrays around), but I would probably use merge sort. Worst case O(n log n) comparisons, and it's conceptually quite simple (split the list in half, sort each half, then you just have to combine the sorted lists in a way that preserves ordering).

-
Tee merge sort is indeed easier to understand then quick sort. –  Ophir Yoktan Mar 17 '11 at 7:04

I'd go with a quick sort. A naive implementation is dead simple to implement and understand:

``````def qsort(arr):
if len(arr) < 2:
return arr
return qsort([x for x in arr[:-1] if x <= arr[-1]]) + [arr[-1]] + \
qsort([x for x in arr[:-1] if x > arr[-1]])
``````

A good implementation requires more work, and the effects of implementation quality can be teachable. For example, even a naive implementation is usually O(N log N) but can be quadratic for pathological inputs. A good implementation makes these pathological inputs as unlikely as possible, which is sometimes more an art than a science. Furthermore, it allows you to introduce the concept of space complexity, since a naive implementation requires O(N log N) space, while a production implementation requires O(log N) space.

-
"even a naive implementation is usually O(N log N) but can be quadratic for pathological inputs": I have done some tests with a naive implementation of quick sort and a naive implementation of merge sort using some random data. Quick sort gets much much slower for data sets that contain between 10000-100000. IMO fast implementations of quick sort require some work or even some hybrid method like intro sort. –  Giorgio Jul 31 at 5:53

There's a bit of a sliding scale for learning the sorting algorithms. Here was my experience at 2 separate colleges (identical flow for learning)

First hit arrays (all are O(n^2) or worse)

• Insertion sort
• Selection sort
• Bubble Sort

• Quick sort
• Merge Sort

• Heap Sort
• Red/Black, AVL, more theory/computationally difficult sorts blah blah blah

I would say the best with the least depth that are O(n^2) or better would be a 2-way quick sort; which, if you're feeling rather sadistic to whom is learning it, have them write it without using recursion. And it can also be expanded into a 3-way divided method as well for more learning/practice.

-

I think tree sort is pretty simple; you just build a binary tree, then traverse it.

-
That's a non comparative sort, and is near linear. But once the tree's built, what happens if you want to add another value, you end up using Heap Sort or Red/Black or AVL or some other map/tree sorting method to get it back to a "binary" state. –  Jeff Langemeier Mar 17 '11 at 18:27
@Jeff, I think you should rethink your comment. You can construct a binary tree using only the less than operator making it a comparison sort. O(n) time on average is impossible for a comparison sort. Tree sort is O(n log n). You can go from a sorted list to a binary tree in linear time, not that it matters, you can't insert a value into an array faster than O(n) time and the question was about sorting. –  dan_waterworth Mar 17 '11 at 20:09
I figured that we would want something that was balanced for easier searching, but I figure if you just want to go off of building a tree without balance the way that you stated will be fine. As an aside though, the students would have to know about either a way to use an array to "simulate" a tree or some sort of linked list type system, which could be more headache than it's worth. –  Jeff Langemeier Mar 18 '11 at 0:47