How does native sort method deal with sparse arrays

user_8234457 0
Viewed 204

When a sparse array is sorted [5, 2, 4, , 1].sort() -> [1, 2, 4, 5, empty], the empty value is always last even with callback no matter the return statement.

I'm building my own sort method as a challenge and I solved this problem by using filter method since filter skips empty values. Then iterate over filtered array and set original array's index to filtered array's values. Then I shorten the original array's length since the remaining items will be duplicates, and I can finally feed it in my sorting algorithm. Once that's done, then I set it's length back to original which adds appropriate amount of empty items at the end. Here's a snippet of code, but here's a link of the entire code

const collectUndefined = [];

// remove empty items and collect undefined
const removeSparse = this.filter(el => {
  if (el === undefined) {
    collectUndefined.push(el);
  }

  return el !== undefined;
});

const tempLength = this.length;

// reset values but will contain duplicates at the end
for (let i = 0; i < removeSparse.length; i++) {
  this[i] = removeSparse[i];
}

// shorten length which will remove extra duplicates
this.length = removeSparse.length;



// sort algorithm ...



// place undefineds back into the array at the end
this.push(...collectUndefined);

// restores original length and add empty elemnts at the end
this.length = tempLength;
return this

Is the native sort implemented in this similar fashion when dealing with sparse arrays, or no.

sorting arrays javascript
1 Answers

When it comes to implementation of Array.sort you have to also ask which engine? They are not all equal in terms of how they end up getting to the final sorted version of the array. For example V8 has a pre-processing and post-processing step before it does any sorting:

V8 has one pre-processing step before it actually sorts anything and also one post-processing step. The basic idea is to collect all non-undefined values into a temporary list, sort this temporary list and then write the sorted values back into the actual array or object. This frees V8 from caring about interacting with accessors or the prototype chain during the sorting itself.

You can find pretty detailed explanation of the entire process V8 goes through here

The actual source code for the V8 sort (using Timsort) can be found here and is now in Torque language.

The js tests for V8 Array.sort can be seen here

Bottom line however is that nothing is actually removed from the original array since it should not be. Sort is not supposed to mutate the original array. That would be super weird if you call myArray.sort() and all of a sudden it has 5 elements less from its 8 total (for example). That is not something you would find in any Array.sort specs.

Also Array.sort pays close attention to the types it sorts and orders them specifically. Example:

let arr = [4,2,5,,,,3,false,{},undefined,null,0,function(){},[]]

console.log(arr.sort())

Notice in the output above how array is first, followed by numeric values, object literal, Boolean, function, null and then undefined / empty. So if you want to really match the spec you would have to consider how different types are also sorted.

user_1558190
Related