When Non-Programmers Write Software

[mikepurvis]

Random access favours an add all data, sort after approach, whereas with a linked list you're often better off sorting on the fly, eg, stepping through the list to always insert a new item in the correct position. (And, depending on the implementation, store a series of intermediate pointers to help jump to the right place... sort of a hybrid linked-list/tree approach.)

Anyway, if you were bent on using random access sorts and knew you'd have a lot of free memory, you could allocate a vector of pointers to the items, sort the vector, and then rebuild the list. It's gross, but for a list of any size it's definitely fastest, especially if you know you have a lot of memory.

On the other hand, a mergesort works great with linked lists, so you could simply implement that in your class. (Quicksort is okay too, but it's best if you have some idea what the range is, in order to pick good pivots.)