american flag sort optimization

Question

I am trying to implement American Bucket Sort. Wiki says "first to count the number of objects that will fall in each bin, and second to place each object in its bucket."

In second phase, when placing objects in proper buckets, Do I need to use auxiliary array? Is there a way to do this by swapping array elements in linear time?

Answer 1

Assuming you mean http://en.wikipedia.org/wiki/American_flag_sort, then as the article points out at the top, you can run this in-place (although then this is not a stable sort). The main idea is to have a pointer to the first item not read in, initially 0, and a temporary variable to hold one item.

As the first step you look at the pointer and pick up the item it points it. Now you can use the indexes to put it in place. Unless its place is the position you originally read from, you are about to overwrite another item, so you swap the item you have picked up with the item you would overwrite, and you are now holding a different temporary item - and look up to see where it should go and carry on.

Eventually you have put something into the place you read from, so you can increment the read pointer, skipping over areas where you have already written sorted items, pick up a different item, and carry on until everything is sorted.