Post
by **filigabriel** » Tue Feb 08, 2005 12:44 am

I'm not sure if your algorithm is fast. In order to count the minimun number of swaps, you should use a 64-bit integer, because of in the worst case [ 500000, 499999, 499998, .... , 1 ] you need (500,000) * (499,999) / 2 swaps and that number doesn't fit into a 32-bit integer.

My implementation use a divide&conquer algorithm.

Hint. Is well known that making a sorted list from two sorted lists is O(n), and counting minimun necessary swaps for processing it is relatively easy.