What is the easiest non-quadratic sorting algorithm?

Question

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.

Answer 1

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.

Answer 2

Shell sort has complexity O(n^3/2). Maybe not easier to explain, but easier to implement correctly.

Answer 3

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

Answer 4

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

Learned about recursion

• Quick sort
• Merge Sort

Learned about binary trees

• 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.

Answer 5

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.

Answer 6

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).

Answer 7

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.