<p>Say I have a list class which has a <code>sort</code> method.</p>
<pre><code>class List { // the standard library list class for a language
    // ...
    method sort {/*...*/}
    // ...
} 
</code></pre>
<p>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.</p>

<language-design><standard-library>
Should the method to sort a list modify it in-place or return a new object?
CC BY-SA 4.0
2023-05-17T23:29:27.067Z
For the efficiency side of the question cs may be a better place to look. E.g. https://cs.stackexchange.com/questions/3/why-is-quicksort-better-than-other-sorting-algorithms-in-practice
Bruce Adams
<p>Returning a copy is more flexible.</p>
<p>This JavaScript implementation of a <code>List</code> class has both:</p>
<pre class="lang-js prettyprint-override"><code>    class List {
      constructor(a) {this.data=a;}
      sort() {return this.data.sort();}
      sorted() {return [...this.data].sort();}
    }
</code></pre>
<p>Creating a new <code>List</code> is simple:</p>
<pre class="lang-js prettyprint-override"><code>    x=['c','g','a','d','b'];
    y=new List(x);
</code></pre>
<p>The <code>sort()</code> method mutates not only <code>y.data</code> but also <code>x</code>:</p>
<pre class="lang-js prettyprint-override"><code>    console.log(y.data);
    console.log(y.sort());
    console.log(y.data);
    console.log(x);
</code></pre>
<p>If you use the <code>sorted()</code> method, <code>x</code> and <code>y.data</code> are left unchanged.</p>
<pre class="lang-js prettyprint-override"><code>    console.log(y.data);
    console.log(y.sorted());
    console.log(y.data);
    console.log(x);
</code></pre>
<p><code>y.data</code> can be changed by assigning the returned array from <code>sorted()</code>:</p>
<pre class="lang-js prettyprint-override"><code>    y.data=y.sorted();
</code></pre>

CC BY-SA 4.0
2023-05-18T14:46:10.013Z
2023-05-31T06:21:19.457Z
2023-05-31T06:21:19.457Z
JMP
<h1>Functional but In-Place</h1>
<p>Semantically returns a new copy, and then optimize it into an inplace operation according to the subsequent process.</p>
<h2>Reference</h2>
<ul>
<li><a href="https://www.microsoft.com/en-us/research/uploads/prod/2020/11/perceus-tr-v4.pdf" rel="nofollow noreferrer">FBIP: Functional but In-Place Reuse Analysis</a></li>
<li><a href="https://www.microsoft.com/en-us/research/uploads/prod/2023/05/fbip.pdf" rel="nofollow noreferrer">FP²: Fully in-Place Functional Programming</a></li>
</ul>
<p>For FBIP sort, you can refer to <code>FP² chapter 4.2</code>.</p>
<p>Note that the unit of inplace/reuse analysis is not the <code>sort</code> operation, but the elements' allocate actions, which is more flexible and powerful.</p>
<h2>Who Use This Feature</h2>
<ul>
<li><a href="https://koka-lang.github.io/koka/doc/book.html#sec-fbip" rel="nofollow noreferrer">Koka</a></li>
<li><a href="https://github.com/leanprover/lean4" rel="nofollow noreferrer">Lean4</a></li>
</ul>

CC BY-SA 4.0
2023-06-27T09:00:49.970Z
2023-06-27T09:00:49.970Z
Aster
CC BY-SA 4.0
2023-06-27T18:33:02.990Z
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?
Arnaud Le Blanc
<h1>In-place + a <code>copy</code> method for lists</h1>
<p>This provides the efficiency benefits of in-place sorts, while creating a new sorted list is still possible (and convenient).</p>

CC BY-SA 4.0
2023-05-18T01:02:08.597Z
2023-05-18T01:02:08.597Z
ice1000
<h1>New Object</h1>
<p>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.</p>

CC BY-SA 4.0
2023-05-17T22:40:54.990Z
2023-05-17T23:04:03.360Z
2023-05-17T23:04:03.360Z
naffetS
CC BY-SA 4.0
2023-05-17T22:48:54.763Z
Mutable types aren't a problem if you use CoW.
Bbrk24
CC BY-SA 4.0
2023-05-17T23:02:31.923Z
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](/help/how-to-answer).
Community Compiler
<h1>Why not both?</h1>
<p>Swift has a mutating method <code>.sort()</code>, and a method that returns a copy <code>.sorted()</code>. The former is only implemented for a couple of types like arrays, but the latter can be implemented for a lot of things.</p>

CC BY-SA 4.0
2023-05-17T22:32:02.547Z
2023-05-17T22:32:02.547Z
Bbrk24
CC BY-SA 4.0
2023-05-18T10:51:12.220Z
Same deal for other languages. For Ruby - there's [Array#sort](https://docs.ruby-lang.org/en/3.2/Array.html#method-i-sort) which returns a new array with sorted elements, and [Array#sort!](https://docs.ruby-lang.org/en/3.2/Array.html#method-i-sort-21) 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.
Mark Glossop
CC BY-SA 4.0
2023-06-27T15:27:48.617Z
Python also has `v.sort()` (in place) and `sorted(v)` (sorted copy).
CoffeeTableEspresso
CC BY-SA 4.0
2023-10-02T17:42:31.393Z
Kotlin's situation is the same: a `sort` on `MutableList` and `sorted` on `List`
Seggan
# Should the method to sort a list modify it in-place or return a new object?
Posted by: username_0 on 2023-05-17
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.
**Tags:** language-design standard-library
> **Comments:**
> **username_1**: For the efficiency side of the question cs may be a better place to look. E.g. https://cs.stackexchange.com/questions/3/why-is-quicksort-better-than-other-sorting-algorithms-in-practice  
---
## 5 answers
### Answer by username_7 on 2023-05-17. Score: 12
# 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.
> **Comments:**
> **username_9** (2023-05-18): Same deal for other languages. For Ruby - there's [Array#sort](https://docs.ruby-lang.org/en/3.2/Array.html#method-i-sort) which returns a new array with sorted elements, and [Array#sort!](https://docs.ruby-lang.org/en/3.2/Array.html#method-i-sort-21) 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.  
> **username_10** (2023-06-27): Python also has `v.sort()` (in place) and `sorted(v)` (sorted copy).  
> **username_11** (2023-10-02): Kotlin's situation is the same: a `sort` on `MutableList` and `sorted` on `List`  
---
### Answer by username_2 on 2023-05-18. Score: 5
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();
---
### Answer by username_3 on 2023-06-27. Score: 4
# Functional but In-Place

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

## Reference

* [FBIP: Functional but In-Place Reuse Analysis](https://www.microsoft.com/en-us/research/uploads/prod/2020/11/perceus-tr-v4.pdf)
* [FP²: Fully in-Place Functional Programming](https://www.microsoft.com/en-us/research/uploads/prod/2023/05/fbip.pdf)

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

* [Koka](https://koka-lang.github.io/koka/doc/book.html#sec-fbip)
* [Lean4](https://github.com/leanprover/lean4)
> **Comments:**
> **username_4** (2023-06-27): 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?  
---
### Answer by username_5 on 2023-05-18. Score: 3
# 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).
---
### Answer by username_6 on 2023-05-17. Score: 3
# 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.
> **Comments:**
> **username_7** (2023-05-17): Mutable types aren't a problem if you use CoW.  
> **username_8** (2023-05-17): 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](/help/how-to-answer).  
---
