Talk:Sort disjoint sublist
Adapted from a question/answer here. Note that the solution for languages with pointers might be different than the Python as you may be able to adapt a sort routine to sort via an extra level of indirection. --Paddy3118 06:34, 12 February 2011 (UTC)
- ... Which has just been done by the Go example. Sweet! --Paddy3118 06:02, 14 February 2011 (UTC)
- I expect that swapping through a level of indirection to be less efficient than extracting the values, sorting them, then putting them back, for typical machine architectures and random sorts. --Rdm 12:58, 14 February 2011 (UTC)
- I wouldn't want to call that either way; depends on too many factors (notably whether cache limits are observed). Only way to know is to measure in a realistic setting. –Donal Fellows 16:42, 14 February 2011 (UTC)
- I expect that swapping through a level of indirection to be less efficient than extracting the values, sorting them, then putting them back, for typical machine architectures and random sorts. --Rdm 12:58, 14 February 2011 (UTC)
Indices as collection
I see that many languages take the indices as a general collection (or array) instead of specifically as a set. If they're doing that, should they also be enforcing uniqueness of the indices before progressing with the rest of the sort? (To be exact, failing to do this gives wrong answers…) –Donal Fellows 16:45, 14 February 2011 (UTC)
- The task states that 6, 1, and 7 are given. I didn't want people to assume they got 1,6,7 in that order. I would therefore be inclined to not insist that a routine should also account for duplicates. (Although I had noted this addition in the TCL example which is fine). --Paddy3118 17:01, 14 February 2011 (UTC)
- It seems like having duplicate indicies wouldn't change the outcome, but it would waste a few cycles reassigning the same number to the same index. some computer languages might not work like my brain though. --Mwn3d 18:21, 14 February 2011 (UTC)
- The problem is that the repeated indices will not, in general, correspond to the location of the repeated data, once the data is sorted. --Rdm 18:25, 14 February 2011 (UTC)
- It seems like having duplicate indicies wouldn't change the outcome, but it would waste a few cycles reassigning the same number to the same index. some computer languages might not work like my brain though. --Mwn3d 18:21, 14 February 2011 (UTC)