recreating array sort method

mySort.js

// Array prototype method, however this is not safe, since it is added to the global scope
// definedProperty makes method non-enumerable as well as adding new property to in this case, to Array prototype
// Array prototype method, however this is not safe, since it is added to the global scope
// definedProperty makes method non-enumerable as well as adding new property to in this case, to Array prototype
Object.defineProperty(Array.prototype, 'mySort', {
  value: function(callback) {
    const mergeSort = arr => {
      if (arr.length === 1) {
        return arr;
      }
      const mid = Math.floor(arr.length / 2);
      const left = arr.slice(0, mid);
      const right = arr.slice(mid);

      return merge(mergeSort(left), mergeSort(right));
    };

    const merge = (left, right) => {
      const result = [];

      let leftIdx = 0;
      let rightIdx = 0;
      while (leftIdx in left && rightIdx in right) {
        if (callback) {
          const num = callback(left[leftIdx], right[rightIdx]);
          // chrome doesn't sort array if comparison function returns a boolean
          // if (typeof num === 'boolean') {
          //   return result.concat(left.slice(leftIdx), right.slice(rightIdx));
          // }
          if (num > 0) {
            result.push(right[rightIdx]);
            rightIdx++;
          } else {
            result.push(left[leftIdx]);
            leftIdx++;
          }
        }
      }

      return result.concat(left.slice(leftIdx), right.slice(rightIdx));
    };
    
    if (typeof callback !== 'function' && callback !== undefined) {
      throw new TypeError(
        'The comparison function must be either a function or undefined'
      );
    }
    
    // following V8 steps https://v8.dev/blog/array-sort#before-sort

    // 1. remove all undefineds and holes
    // 2. All non-undefined values are sorted
    // 3. add undefineds followed by holes back to sorted values at the end --> https://www.ecma-international.org/ecma-262/10.0/index.html#sec-sortcompare

    // first remove undefineds and empty items. Then store items in new(temp) list
    let countUndefined = 0;

    let tempList = this.filter(el => {
      if (el === undefined) {
        countUndefined++;

        return false;
      }

      return true;
    });

    // then sort that temporarily list, in this case we using merge sort(bottom up)
    // if we wanted to stay true to V8, we would use TimSort, which is an adaptive
    // stable merge sort variant https://github.com/python/cpython/blob/master/Objects/listsort.txt
    tempList = mergeSort(tempList);
    // sorting is done, tempList must be written back into the original unsorted array

    // there's an actual TimSort npm package
    // it's close enough to V8 TimSort, which is written in Torque https://github.com/v8/v8/blob/78f2610345fdd14ca401d920c140f8f461b631d1/third_party/v8/builtins/array-sort.tq#L5
    // one sorting difference is when handling crazy arrays with different types of elements
    // such as [1, ,null, 5, undefined, NaN, [], function() {}, 'a', Infinity, {}, , ,]
    // **this shouldn't matter because there's no real world case for sorting this type of array
    //   and different browsers have different outputs

    //[5, ,null, 1, undefined, NaN, [], function() {}, 'a', Infinity, {}, , ,].sort((a, b) => a - b)

    // safari 12.1.1 [null, Array(0), 1, 5, NaN, ƒ, "a", Infinity, {…}, undefined, empty × 3]
    // chrome        [5, {…}, null, 1, Infinity, NaN, Array(0), ƒ, "a", undefined, empty × 3]
    // firefox       [{…}, Infinity, "a", ƒ, null, Array(0), NaN, 1, 5, undefined, empty × 3]
    // edge          [5, {…}, null, 1, Infinity, NaN, Array(0), ƒ, "a", undefined, empty × 3]
    // ie 11         [5, {…}, null, 1, Infinity, NaN, Array(0), f, "a", undefined, undefined, undefined, undefined, undefined] **console error, displays extra undefined --> https://stackoverflow.com/a/56832051/8234457

    // safari 12.1.1 [[], 1, 5, Infinity, NaN, {}, "a", function, null, undefined]

    // const TimSort = require('timsort')
    // TimSort(arr, callback)

    const tempListLength = tempList.length + countUndefined;

    // since the tempList length is extended by countUndefined
    // the last iterations will result in out-of-bounds values,
    // which will add the correct amount of undefineds at the end of the array
    for (let i = 0; i < tempListLength; i++) {
      this[i] = tempList[i];
    }

    // original array now has correct sorted elements but
    // since tempList was sorter due the removal of items,
    // original array has extra items at the end which could be duplicates
    const temp = this.length;

    // sorten the length of array which removes duplicates
    this.length = tempListLength;
    // set original length back which adds correct amount of empty items at the end of the array
    this.length = temp;

    // result is sorted array with undefineds and empty values set to last in that order
    return this;
  },
});