make unstable sorts stable

For any unstable sort, we can make it stable with this simple technique.

Aha — I have to assume two items of equal key have visible differences such as address. If they are indistinguishable then sort stability is moot.

I will first build a hashtable {address -> origPos}

After the unstable sort, all the items with same key=77 will cluster together but not in original order. Within this segment of the output, I will run another mini-sort based on the origPos values.

This doesn’t affect time complexity. In terms of space complexity, it’s O(N).

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s