Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – How to write array sort polyfill using merge sort approach

I was trying to write a Polyfill for array sorting in javascript. However it turns out that the comparator doesn’t cause any effect on the Polyfill. Any ideas how to make it work?

const arrA = [2, 3, 4, 1, 2, 3, 1, 5, 6, 8, 5, 9, 3];
const newArr = [...new Set(arrA)];

Array.prototype.myNewSort = function(compareFn) {
  return mergeSort(this);

  function mergeSort(arr) {
    if (arr.length <= 1) 
      return arr;

    const mid = Math.floor(arr.length / 2);
    const leftArr = arr.slice(0, mid);
    const rightArr = arr.slice(mid);

    return merge(mergeSort(leftArr), mergeSort(rightArr));
  }

  function merge(left, right) {
    let newArr = [];

    while (left.length > 0 && right.length > 0) {
      let newCompareFn = compareFn ? compareFn = (l, r) => l < r : newCompareFn;
      newCompareFn = (left, right) => left > right;
      if (newCompareFn(left[0], right[0])) {
        newArr.push(left.shift());
      } else {
        newArr.push(right.shift())
      }
    }

    return [...newArr, ...left, ...right];
  }

  function composeCompareFn(compareResult) {
    if (Math.sign(compareResult) === -1) return false;
    if (Math.sign(compareResult) === 1) return true;
    if (compareResult === 0) return false;
  }
}

const sortedArr = newArr.myNewSort((a, b) => a - b);
console.log("sortedArr", sortedArr);
Tags:

2

Answers


  1. Chosen as BEST ANSWER
    0

    Updated Code:

    const arrA = [2,3,4,1,2,3,1,5,6,8,5,9,3];

const newArr = [...new Set(arrA)];
console.log("new arr", newArr);

Array.prototype.myNewSort = function(compareFn) {
    return mergeSort(this);
  
  function mergeSort(arr) {
    if(arr.length <= 1) return arr;
    
    const mid = Math.floor(arr.length / 2);
    const leftArr = arr.slice(0, mid);
    const rightArr = arr.slice(mid);
    
    return merge(mergeSort(leftArr), mergeSort(rightArr));
  }
  
  function merge(left, right) {
    let newArr = [];
    
    while(left.length > 0 && right.length > 0) {
        if(composeCompareFn(compareFn(right[0], left[0]))) {
        newArr.push(left.shift());
      } else {
        newArr.push(right.shift())
      }
    }
    
    return [...newArr, ...left, ...right];
  }
  
  function composeCompareFn(compareResult) {
    if(Math.sign(compareResult) === -1) return false;
    if(Math.sign(compareResult) === 1) return true;
    if(compareResult === 0) return false;
  }
}

const sortedArr = newArr.myNewSort((a, b) => b - a);
console.log("sortedArr", sortedArr);

  2. 0

    Let’s look at:

      let newCompareFn = compareFn ? compareFn = (l, r) => l < r : newCompareFn;
  newCompareFn = (left, right) => left > right;

    If compareFn was passed to the function, the first line will reassign it. That doesn’t matter, however, because the next line overrides the first assignment to newCompareFn with yet another function. (Note that if the compareFn parameter is not passed, newCompareFn will be set to undefined. Again, however, that does not matter, because it’s reassigned in the next line.)

    If you want to use the comparator function passed as a parameter, there’s no need for performing any reassignments like that; just use the function.

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search