Optimizing a cycle sort implementation

Question

Cycle sort is an in-place sort based on the idea that the permutation you're sorting can be factored into cycles. If you rotate each cycle one position, the array will be sorted. This can easily be coded so that the number of writes to the array is the theoretical minimum needed for any in-place sort (which is nice for huge data sets on, say, Flash drives, where you want to minimize the number of writes to the device).

Are there any ways to improve the run time of the code on Wikipedia while keeping it an in-place sort and maintaining the optimal number of writes or is it the best it can be?

Here is the implementation (note that range(a, b) goes from a to b - 1) :

# Sort an array in place and return the number of writes.
def cycleSort(array):
  writes = 0
  # Loop through the array to find cycles to rotate.
  for cycleStart in range(0, len(array) - 1):
    item = array[cycleStart]
    # Find where to put the item.
    pos = cycleStart
    for i in range(cycleStart + 1, len(array)):
      if array[i] < item:
        pos += 1
    # If the item is already there, this is not a cycle.
    if pos == cycleStart:
      continue
    # Otherwise, put the item there or right after any duplicates.
    while item == array[pos]:
      pos += 1
    array[pos], item = item, array[pos]
    writes += 1
    # Rotate the rest of the cycle.
    while pos != cycleStart:
      # Find where to put the item.
      pos = cycleStart
      for i in range(cycleStart + 1, len(array)):
        if array[i] < item:
          pos += 1
      # Put the item there or right after any duplicates.
      while item == array[pos]:
        pos += 1
      array[pos], item = item, array[pos]
      writes += 1
  return writes

Answer 1

The expensive part of this algorithm is figuring out where each item goes. The rest of it is just applying a permutation one cycle at a time. This code takes O(n^2) figuring out where the items go and O(n) to actually move them.

If you're willing to use some temporary storage (DRAM instead of flash, say), you could make it much faster by using a temporary array of pointers, sorting that, and then using the result to move the actual data. This is how you would sort large records where the cost of moving them repeatedly is prohibitive.

If you aren't allowed to have O(n lg(n)) bits of auxiliary storage, I think you might be out of luck. Just recording which permutation to do requires log(n!) = O(n lg(n)) bits of storage. So you would need to compute the permutation incrementally (like cycleSort does) and I don't see any way to do that cheaply.