### Linear Time Sort Puzzler

Interviewing for an engineering position at Google can be grueling and humbling. You get less than an hour with each interviewer, and may get one technical problem after another to solve. If you have performance anxiety you may have a hard time focusing on the problem. The best approach, if you can do it, is to think of the interview as a technically challenging but friendly brainstorming session. If you get hired, that's what your life will be like.

My friend, Jim Davis, told me about someone he interviewed earlier this week.
The candidate thought
the interview wasn't going well and hoped to impress Jim by
sharing an idea he had: a new algorithm for sorting in linear time. It
isn't a sort based exclusively on comparisons; it can be proven that any
such sort must perform O(*n* log *n*) comparisons. It isn't
a bucket sort, which is a standard algorithm for this problem (assuming
certain characteristics of the input set). But the candidate's algorithm
helped Jim understand the candidate's capabilities.

The algorithm works like this: you start by making a linear scan through
the *n* numbers to be sorted and note the largest and smallest of the
elements. Using that, you compute a linear function *f(x)* that will
map the smallest input element to zero and the largest to *n*. Then,
for each input element *x _{i}*, you fork a task that waits

*f(x*milliseconds and then outputs

_{i})*x*. After

_{i}*n*milliseconds the output contains the input elements in sorted order.

There may be problems when two tasks attempt to output their data at
nearly the same time, but let's ignore that for a moment and assume an
"ideal" system. If you have a truly concurrent computer, this
may run in O(*n*) time using O(*n*) processors, thereby
consuming a total of O(*n ^{2}*) processing time. There are
far better concurrent sorting algorithms around. Much more interesting
is the idea of running this algorithm on a sequential computer with a
non-preemptive scheduler. The non-preemptive scheduler avoids the problem
of two tasks producing data at the same time. The scheduler can also ensure
that the tasks run in their proper order, even if the running time of some
tasks causes others to start slightly "too late".

Jim explained the problem with the algorithm, concluding "so you've reduced the problem of sorting in linear time to a different linear time sorting algorithm." After Jim explained this remark, the candidate replied "well, the idea isn't really very well thought out." Here is the puzzle: what was Jim talking about?