In my project I have a list of items that should be sorted, but instead of re-arranging the positions of the items in the array I want to set a 'Sequence' property defining the item's places in the list.

Currently I use a merge sort to re-arrange the array and then loop over the items to set their sequence property.
Are there more efficient ways to do this?
Is there a researching term I am missing or maybe this is this the fastest way already?


These days, most of the time you're sorting records of any kind, you're really only sorting pointers to them, while the records stay where they are in memory. That means that performing a sort and then a relabelling is effectively no more expensive than normal sorting, since the sort is likely to be superlinear and the relabelling is linear in time, and there is no big constant to mess things up.

Only if you actually do have an array of raw memory and sorting physically shuffles records around is it useful to invent a cleverer solution to avoid the shuffling. Usually, the solution will be to essentially introduce a layer of pointers to the records, just like most collections already do.

  • I understand that setting pointers isn't much work. I was just thinking that looping through the collection twice could be wasteful. Mar 3 '17 at 9:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.