It is possible to do it in O(n) time and O(1) space apparently. The paper Stable minimum space partitioning in linear time by Jyrki Katajainen, and Tomi Pasanen claims to be able to do it. Google for stable 0-1 sort.
Assuming the list of IDs isn’t too large, you could convert the QS to a list and sort it in Python: album_list = list(albums) album_list.sort(key=lambda album: album_ids.index(album.id))
No, you cannot rely on that unfortunately. Let’s assume you have the array (two fields in each record used for checking but only first field used for sorting): B,1 B,2 A,3 A non-stable sort may compare B,1 with A,3 and swap them, giving: A,3 B,2 B,1 If the next step were to compare B,2 with … Read more
We can use sortrows as a preprocessing step to sort the indices and corresponding values first, as its documentation states: SORTROWS uses a stable version of quicksort. As the subscripts in subs should be sorted with respect to their linear indices, we need to sort them in reverse lexicographic order. This can be achieved by … Read more
Yes, the intention of the manual is indeed to guarantee that sorted is stable and indeed that it uses exactly the same algorithm as the sort method. I do realize that the docs aren’t 100% clear about this identity; doc patches are always happily accepted!
As of ES2019, sort is required to be stable. In ECMAScript 1st edition through ES2018, it was allowed to be unstable. Simple test case (ignore the heading, second set of numbers should be sequential if the engine’s sort is stable). Note: This test case doesn’t work for some versions of Chrome (technically, of V8) that … Read more