The worst sort algorithm in the world!

In interviewing candidates for programming jobs we have tried to come up with some unusual technical questions. Mostly this is to observe the person's reaction to such a question and to see how they might try to solve the problem.

My latest favorite question in this vein is this: "What is the worst sort algorithm you can think of?" The more precise problem definition is that the algorithm must be guaranteed to terminate and that the input will be sorted. Typically bad sort is a bubble sort - whose execution complexity is O(N^2) in the worst case.

But can you do better? Or rather, can you do worse?!

Here is an algorithm that in the worse case is O(N!) - where N! stands for N factorial (i.e. N*(N-1)*(N-2)...2*1). It works like this:

• Take random permutation from the set of permutations of N elements
• Apply this permutation to the input
• If not yet sorted, choose another permutation and go back to previous step

Since there are N! permutations of N elements, on average N!/2 permutations will have to be tried. So the execution complexity of this algorithm will be O(N!).

Just to try it out I wrote this sort in Ruby. Here is the code:

require "permutation"

class Array
  # return true if array is sorted
  def sorted?
    return true if self.length <= 1      
    for i in 0..self.length-2         
      return false if (self[i] > self[i+1])
    end
    true
  end
end

def worst_sort (a)
   perm = Permutation.new(a.length)
   while (perm.rank != perm.last)
      sa = perm.project(a)
      return sa if (sa.sorted?)
      perm.succ!
   end
end

I tried running this sort on my laptop and for an array of 11 elements it was taking so long that I lost patience and stopped the program.

If you look at the code above the most difficult part is generating permutations on N elements in order. I was lucky to find that the hard work was already done for me in the Ruby "permutations" module. You can find the source for this module here: http://permutation.rubyforge.org.