If memory were not scarce, how would you implement a sort in a language with libraries for representing and sorting sets

Question

If memory were not scarce, how would you implement a sort in a language with libraries for representing and sorting sets

Answer 1

A set is unordered, so sorting sets is useless. A "sorted" set is the same as the set itself, even with scarce memory.

To represent a set in non-scarce memory, is just like representing a set in scarce memory. However, if memory is not scarce, we could create a binary predicate for each value or object in memory, stating: "I'm member of set X".

If you want to check whether object Y is member of set X, then just check the binary predicate; which is either true or false.

The iteration of all objects in a set is like an array. It can also be implemented as a double-linked-list or using a hashtable. The difference is all in the details; what objects do you want in the set?

If memory were not scarce, and you've got enough horse-power in your CPU left, then I would store every hash value of an object in memory, instead calculating it on the fly. Then, a hashtable-esque implementation of a set is really fast for listing capabilities. Adding/removing objects from the set is rather slow.

If adding/removing is more needed than listing, any linked-list will do.

Both ways could use the predicate value for each object. It depends on your requirements; for instance, do you allow two objects simultaneously in two sets? (Generally this is a "yes"), then you'll need an array/linked-list storage for each object in the set, to store it's membership information.

There is no "one right" solution, though. Just my two pennies.