6
$\begingroup$

Say I have a list class which has a sort method.

class List { // the standard library list class for a language
    // ...
    method sort {/*...*/}
    // ...
} 

Should this method, when called, sort the list in-place or return a new sorted list? I don't know which is more efficient and which is more user-friendly/expected behaviour.

$\endgroup$
1

5 Answers 5

12
$\begingroup$

Why not both?

Swift has a mutating method .sort(), and a method that returns a copy .sorted(). The former is only implemented for a couple of types like arrays, but the latter can be implemented for a lot of things.

$\endgroup$
3
  • 2
    $\begingroup$ Same deal for other languages. For Ruby - there's Array#sort which returns a new array with sorted elements, and Array#sort! which returns the same array, sorted in-place. For Rust - AFAICT the protocol is to mutate in place; if you want a non-mutating version, you're expected to clone the array first. I expect there are other examples as well. $\endgroup$ May 18, 2023 at 10:51
  • 1
    $\begingroup$ Python also has v.sort() (in place) and sorted(v) (sorted copy). $\endgroup$ Jun 27, 2023 at 15:27
  • $\begingroup$ Kotlin's situation is the same: a sort on MutableList and sorted on List $\endgroup$
    – Seggan
    Oct 2, 2023 at 17:42
5
$\begingroup$

Returning a copy is more flexible.

This JavaScript implementation of a List class has both:

    class List {
      constructor(a) {this.data=a;}
      sort() {return this.data.sort();}
      sorted() {return [...this.data].sort();}
    }

Creating a new List is simple:

    x=['c','g','a','d','b'];
    y=new List(x);

The sort() method mutates not only y.data but also x:

    console.log(y.data);
    console.log(y.sort());
    console.log(y.data);
    console.log(x);

If you use the sorted() method, x and y.data are left unchanged.

    console.log(y.data);
    console.log(y.sorted());
    console.log(y.data);
    console.log(x);

y.data can be changed by assigning the returned array from sorted():

    y.data=y.sorted();
$\endgroup$
0
4
$\begingroup$

Functional but In-Place

Semantically returns a new copy, and then optimize it into an inplace operation according to the subsequent process.

Reference

For FBIP sort, you can refer to FP² chapter 4.2.

Note that the unit of inplace/reuse analysis is not the sort operation, but the elements' allocate actions, which is more flexible and powerful.

Who Use This Feature

$\endgroup$
1
  • $\begingroup$ Koka is able to reuse constructors when they are not live, with seems to work nicely when mapping a tree, but will it work with sorting? $\endgroup$ Jun 27, 2023 at 18:33
3
$\begingroup$

New Object

Mutable lists are known to cause bugs. It's annoying to deep-copy every time you want to do something. You could consider just not supporting mutable lists.

$\endgroup$
2
  • $\begingroup$ Mutable types aren't a problem if you use CoW. $\endgroup$
    – Bbrk24
    May 17, 2023 at 22:48
  • $\begingroup$ Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. $\endgroup$ May 17, 2023 at 23:02
3
$\begingroup$

In-place + a copy method for lists

This provides the efficiency benefits of in-place sorts, while creating a new sorted list is still possible (and convenient).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .