100

Apart for the native way of cloning an array and then sorting it in place, is there an algorithm and existing implementation that is more suited for non-destructive sorting?

Need to sort an array of floats into a new array without changing the source. My search results were rather thin since most of the literature is focused on reducing the memory requirements with in-place sorting.

Using the native sorted = [].slice().sort() works fine. This question is about understanding if there are other performant sorting implementations when memory constraints are removed since a new array is needed anyway.

10
  • "Is there any existing functional sort implementation available? " --- How about [].slice().sort()?
    – zerkms
    May 25, 2015 at 4:37
  • There is no preferred algorithm. It depends on how you want to use it. I’d go with .slice().sort().
    – Ry-
    May 25, 2015 at 4:38
  • 1
    It might be worth microbenchmarking the performance of .slice() vs creating a new array and pushing elements individually. That might be why the libraries you listed don't use an algorithm that builds the resulting array sequentially.
    – Sacho
    May 25, 2015 at 4:44
  • 3
    You should probably explain what you mean "a better way"; better in which way?
    – Ja͢ck
    May 25, 2015 at 5:08
  • 2
    If you're asking for a preferred algorithm, you HAVE to specify what criteria you're measuring it by: performance? minimum memory usage? least impact on garbage collector? most compact code? easiest to understand? most use of built-in functions? Without saying what the measurement criteria is, the question is basically meaningless because "preferred" has no meaning without a very specific context. For example, if you were judging a contest among 5 submissions of preferred algorithms, what would be the exact quantitative criteria by which you would measure each submission?
    – jfriend00
    May 25, 2015 at 5:10

3 Answers 3

138

There's a simpler syntax for immutably sorting an array using ES6 spread operator:

[...array].sort(sortFn)
5
  • 3
    Except that spread doesn't do a deep clone, so if it's an array of objects with many levels, you're kinda SOL with that.
    – robertmain
    Oct 25, 2018 at 16:14
  • 34
    @robertmain, actually, it's better that way. As sorting doesn't change the contained objects either. Cloning the containing objects would kill shallow comparisons in other places, making optimizations very hard.
    – s.meijer
    Nov 12, 2018 at 19:38
  • 2
    I like this method more because of its concise nature.
    – daydreamer
    Apr 7, 2019 at 15:26
  • 1
    It is still an in-place sort on the clone (ie clone then in-place sort the clone). The question is about the potential benefits of an out-of-place sort from source to target.
    – Hurelu
    Aug 14, 2021 at 15:39
  • @s.meijer interesting!...iv always avoided a shallow clone on sorts for this reason but i never really thought about the fact that your not mutating the nested objects within that sort Jan 11, 2022 at 17:38
62

As the comments have repeated a few times:

  1. shuffledArray.slice().sort() is the default way to go.
  2. It's not really clear how we could have a better algorithm / method using the libraries your mentioned.

Seeing as the motivation for non-destructive sorting is related to writing functional code, and you're looking at Ramda...check out Facebook's ImmutableJS library if you haven't already.

Particularly, the Seq. You could start storing your array of floats in a Seq, sort it, and be sure the original Seq remains in the right order. In addition, it utilizes Lazy evaluation. http://facebook.github.io/immutable-js/docs/#/Seq
http://facebook.github.io/immutable-js/docs/#/Seq/sortBy

1
  • Thanks. I have looked at the immutable-js source code and it also uses "clone then in-place native sort" just like underscore, lodash and ramda. Since the algorithm literature is quite focused on in-place sorting to reduce the memory requirements I thought removing that constraint would change things. All the feedback so far suggests not.
    – Hurelu
    May 25, 2015 at 5:36
1

Newer javascript runtime can use Array.prototype.toSorted

Documentation from MDN

const months = ["Mar", "Jan", "Feb", "Dec"];
const sortedMonths = months.toSorted();
console.log(sortedMonths); // ['Dec', 'Feb', 'Jan', 'Mar']
console.log(months); // ['Mar', 'Jan', 'Feb', 'Dec']

const values = [1, 10, 21, 2];
const sortedValues = values.toSorted((a, b) => a - b);
console.log(sortedValues); // [1, 2, 10, 21]
console.log(values); // [1, 10, 21, 2]
2
  • Yes. But it might just clone and do an in-place sort under the hood. I did a quick benchmark and a.slice().sort( (a,b)=>a-b ) is surprisingly faster than a.toSorted( (a,b)=>a-b ). Sorting might be a rare case where more memory does not help and sorting is just always done in place.
    – Hurelu
    Oct 28 at 7:03
  • @Hurelu IMHO, benchmarks on relatively new JavaScript built-in functions have limited significance. The new function's performance may well improve with any browser / JS engine update. For better readability and to clarify the intention to not modify the original array, I'd always recommend using toSorted(), if your setup allows to do so. Nov 14 at 16:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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