Closed Bug 1147091 Opened 5 years ago Closed 4 days ago
TArray needs a stable sort algorithm (Merge Sort)
47 bytes, text/x-phabricator-request
|Details | Review|
nsTArray::Sort is using QuickSort which is not stable (i.e. two items that are equal might be re-ordered). In many cases this property is undesirable. MergeSort is stable and is generally faster than QuickSort. We should add it to nsTArray as an alternative sorting method.
FYI, we could just wrap std::stable_sort() like so: std::stable_sort(begin(), end(), aIsLessThanCompareFunction);
(In reply to Mats Palmgren (:mats) from comment #1) > FYI, we could just wrap std::stable_sort() like so: > std::stable_sort(begin(), end(), aIsLessThanCompareFunction); Probably not actually, since Brian found that "on Mac/Android, std::stable_sort appears to call the copy constructor and copy assignment operator" in bug 1263500. We probably want a version that moves entries when that is possible.
Severity: normal → --
Pushed by email@example.com: https://hg.mozilla.org/integration/autoland/rev/52124dd4510e Add StableSort to nsTArray_Impl. r=froydnj
You need to log in before you can comment on or make changes to this bug.