Home > Software engineering >  How can merge sort according to dates?
How can merge sort according to dates?

Time:09-29

I modified the merge sort to sort according to the createdAt date object. As result, I only got an array with 10 elements, however, the starting array has around 10000 elements. Why is this happening? How can I solve this? Does the problem stem from duplicate items in the array? I have tried also extracting resultArray and adding it as a parameter to the array, in that case, I got only an array long of around 1000 elements. Here code for the mergeSort:

function merge(left, right, sorter,) {
  let result=[],leftIndex = 0,
    rightIndex = 0;

  // We will concatenate values into the resultArray in order
  while (leftIndex < left.length && rightIndex < right.length) {
    if (sorter(left[leftIndex], right[rightIndex])) {
      result.push(left[leftIndex]);
      leftIndex  ; // move left array cursor
    } else {
      result.push(right[rightIndex]);
      rightIndex  ; // move right array cursor
    }
  } 
  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
};
function mergeSort(array, sorter = (num1, num2) => num1 < num2,  ) {
  const half = array.length / 2;

  // Base case or terminating case
  if (array.length < 2) {
    return array;
  }

  const left = array.splice(0, half);
  const right = array.splice(half);
  return merge(
    mergeSort(left, sorter,  ),
    mergeSort(right, sorter,  ),
    sorter, 
  );
}

This is how I call it, I give as a parameter the sorter method which checks which date is before then another:

const sortedArr = mergeSort(
          res,
          (obj1, obj2) => {
            return new Date(obj1.createdAt) < new Date(obj2.createdAt);
          },
        )

CodePudding user response:

There are two issues in mergeSort:

  • The / operator does not perform integer division, so the result can be a non-integer number, which does not play well with array indices. Correct to:

    const half = array.length >> 1; // Integer division by 2.
    
  • splice mutates the array on which you use this method: it removes those entries from the array. That means, the second time you call splice, you'll get an empty array or at most one element. Instead use slice.

  • Related