October 25, 2013
I’ve been reading Pessimal Algorithms and Simplexity Analysis by Andrei Broder and Jorge Stolfi. It’s fun. They write three programs: search for an item in a sorted array, enumerate all items in a connected graph, and sort an array into ascending order; we’ll look at the sorting algorithm, but you may want to look at the others yourself. Here is their sorting algorithm:
The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.
To get a ﬁrmer grasp of the multiply and surrender method, let us follow the step-by-step development of the slowsort algorithm. We can decompose the problem of sorting n numbers Al, A2, …, An in ascending order into (1) ﬁnding the maximum of those numbers, and (2) sorting the remaining ones. Subproblem (1) can be further decomposed into (1.1) ﬁnd the maximum of the ﬁrst [n/2] elements, (1.2) ﬁnd the maximum of the remaining [n/2] elements, and (1.3) ﬁnd the largest of those two maxima. Finally, subproblems (1.1) and (1.2) can be solved by sorting the speciﬁed elements and taking the last element in the result. We have thus multiplied the original problem into three slightly simpler ones (sort the ﬁrst half, sort the second half, sort all elements but one), plus some overhead processing. We continue doing this recursively until the lists have at most one element each, at which point we are forced to surrender.
I didn’t copy the code from the article; if you go look at it, beware the bug! The time complexity of the algorithm is O(nlog2(n)/2).
Your task is to write the slowsort program; you may also want to write the research and bwfs programs mentioned in the article. When you are finished, you are welcome to read or run a suggested solution, or to post your solution or discuss the exercise in the comments below.