4 ms·

Heapsort is a lovely, simple, O(NlogN) sort that sorts in place (so that it requires no extra space). (Explicitly stating something that is implied by an existi

Heapsort is a lovely, simple, O(NlogN) sort that sorts in place (so that it requires no extra space). (Explicitly stating something that is implied by an existing response). Edit: Whoops, apparently heapsort is not "stable" (not sure what that means actually), sorry.

srgpqt 7y ago
Stable sort means that the order of same elements is preserved. For example, sorting strings by length, strings of the same length would retain the same order between themselves as they had before sorting.
- billforsternz 7y ago
  Thanks for the explanation, makes sense. I was tempted to classify this as "irrelevant to me", but then I remembered an application I had recently where I had values (chess games) that I was sorting which I didn't want to reorder if they were adjacent (as far as the sort was concerned) but not identical. Ended up adding an "original order" field as a sort tiebreaker. As it happens a stable sort would have saved me the pain.
cdirkx 7y ago
A "stable" sorting algorithm preserves the relative order of elements with "equal value". This doesn't really apply if you are only sorting simple values, as there is no difference between a 7 and another 7, but does if you are sorted more complicated objects by some key. Example: sorting 2#a, 1#c, 2#b by only the first number. An algorithm that produces 1#c, 2#b, 2#a is a correct sorting algorithm, but not stable as it changes the order of 2#a and 2#b.
- billforsternz 7y ago
  Thanks for the explanation, interesting.
hinkley 7y ago
Said another way, if I sort my database by user names, the John Smith who has been my customer the longest always comes first in the line of John Smiths. One of the things you can do with a stable sort is to fake complex sorting by iteratively sorting by each criteria. Though I have rarely seen that be practical anywhere other than tabular data.

srgpqt 7y ago

Stable sort means that the order of same elements is preserved. For example, sorting strings by length, strings of the same length would retain the same order between themselves as they had before sorting.

billforsternz 7y ago
Thanks for the explanation, makes sense. I was tempted to classify this as "irrelevant to me", but then I remembered an application I had recently where I had values (chess games) that I was sorting which I didn't want to reorder if they were adjacent (as far as the sort was concerned) but not identical. Ended up adding an "original order" field as a sort tiebreaker. As it happens a stable sort would have saved me the pain.

cdirkx 7y ago

A "stable" sorting algorithm preserves the relative order of elements with "equal value". This doesn't really apply if you are only sorting simple values, as there is no difference between a 7 and another 7, but does if you are sorted more complicated objects by some key. Example: sorting 2#a, 1#c, 2#b by only the first number. An algorithm that produces 1#c, 2#b, 2#a is a correct sorting algorithm, but not stable as it changes the order of 2#a and 2#b.

billforsternz 7y ago
Thanks for the explanation, interesting.

hinkley 7y ago

Said another way, if I sort my database by user names, the John Smith who has been my customer the longest always comes first in the line of John Smiths. One of the things you can do with a stable sort is to fake complex sorting by iteratively sorting by each criteria. Though I have rarely seen that be practical anywhere other than tabular data.