Summary

Slow Sort is a recursive, in-place sorting algorithm created by Andrei Broder and Jorge Stolfi. It was designed as a "pessimal" algorithm to illustrate concepts of profoundly bad complexity. It is based on the principle of multiply and surrender, a parody of the divide and conquer strategy. The algorithm recursively sorts two halves of an array, places the maximum of the entire array at the end, and then recursively sorts the entire array again, except for the newly placed maximum. This final, redundant recursive call is the source of its abysmal performance.

How it Works

• 1. Base Case: If the subarray has one or zero elements, it is already sorted, so return.

• 2. Divide: Split the current subarray A[i...j] into two halves at the middle index m.

• 3. Recursively Sort Halves:

• First, recursively call Slow Sort on the first half A[i...m]. This will eventually place the maximum of this half at index m.

• Second, recursively call Slow Sort on the second half A[m+1...j]. This will place the maximum of this half at index j.

• 4. Find and Place Global Maximum: Compare the maxima of the two halves (A[m] and A[j]). If A[m] is larger, swap them. This guarantees the maximum element of the entire subarray A[i...j] is now at index j.

• 5. Multiply and Surrender: Recursively call Slow Sort on the entire subarray except for the maximum element we just placed: A[i...j-1]. This final step ensures the rest of the elements are sorted, but at an immense computational cost.