CODEWITHSUNDEEP
javascriptalgorithmsortingin-place
Cheng.Lee
Cheng.Lee

Reputation: 186

Is it a in-place sort？

I have read the blog (original link:Computer science in JavaScript: Merge sort) posted by Nicholas C. Zakas. There is a question confused me always.

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).

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?

The code is following:

Solution 1 (not in-place sort):

function mergeSort(items) {
  // Terminal case: 0 or 1 item arrays don't need sorting
  if (items.length < 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));
}

Solution 2 (in-place sort):

function mergeSort(items) {
  if (items.length < 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;
}

Both use the same function merge:

function merge(left, right){
  var result = [],
      il = 0,
      ir = 0;
  while (il < left.length && ir < right.length) {
    if (left[il] < right[ir]) {
      result.push(left[il++]);
    } else {
      result.push(right[ir++]);
    }
  }
  return result.concat(left.slice(il)).concat(right.slice(ir));
}

Upvotes: 3

Views: 2566

Answers (1)

Oriol
Oriol

Reputation: 288120

Yes, both algorithms sort data in a new, different array. That means O(n) extra space is required.

The only difference is that the so called "in-place sort" then empties the original array and fills it with the sorted data. Whether this makes it in-place or not depends on the definition of in-place.

An in-place algorithm is an algorithm which transforms input using a data structure with a small amount of extra storage space.

In-place can have slightly different meanings. In its strictest form, the algorithm can only have a constant amount of extra space, though sometimes anything in o(n) is allowed.

So usually it isn't considered in-place because the extra space complexity is more than o(n).

If you want an in-place sorting algorithm with O(n log(n)) time complexity and O(1) extra space complexity, you can use heapsort. The drawback is that, unlike mergesort, heapsort is not stable.

Upvotes: 3

Related Questions