title: Is it a in-place sort？
body: <p>I have read the blog (original link:<a href="https://www.nczonline.net/blog/2012/10/02/computer-science-and-javascript-merge-sort/" rel="nofollow">Computer science in JavaScript: Merge sort</a>) posted by Nicholas C. Zakas. There is a question confused me always.</p>
  
  <p>The blog explained the concept of merge-sort by JavaScript, the writer has given two solutions for the merge-sort (the first is non in-place, the other is).</p>
  
  <p>Here is my question: I think there is no difference of space complexity between the solution 1 and solution 2. So should it be understood that the so called "in-place sort" is only with whether the input and output is the same array in this case, but nothing to do with the extra space?</p>
  
  <p>The code is following:</p>
  
  <p>Solution 1 (not in-place sort):</p>
  
  <pre><code>function mergeSort(items) {
    // Terminal case: 0 or 1 item arrays don't need sorting
    if (items.length &lt; 2) {
      return items;
    }
    var middle = Math.floor(items.length / 2),
        left = items.slice(0, middle),
        right = items.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
  }
  </code></pre>
  
  <p>Solution 2 (in-place sort):</p>
  
  <pre><code>function mergeSort(items) {
    if (items.length &lt; 2) {
      return items;
    }
    var middle = Math.floor(items.length / 2),
        left = items.slice(0, middle),
        right = items.slice(middle),
        params = merge(mergeSort(left), mergeSort(right));
    // Add the arguments to replace everything between 0 and last item in the array
    params.unshift(0, items.length);
    items.splice.apply(items, params);
    return items;
  }
  </code></pre>
  
  <p>Both use the same function <code>merge</code>:</p>
  
  <pre><code>function merge(left, right){
    var result = [],
        il = 0,
        ir = 0;
    while (il &lt; left.length &amp;&amp; ir &lt; right.length) {
      if (left[il] &lt; right[ir]) {
        result.push(left[il++]);
      } else {
        result.push(right[ir++]);
      }
    }
    return result.concat(left.slice(il)).concat(right.slice(ir));
  }
  </code></pre>