4
\$\begingroup\$

I implemented the following mergesort algorithm in JavaScript, but I want to know your opinion about if is possible to do better than this.

function mergesort(list){
    if(list.length < 2){
        return list
    }else if(list.length > 1){
        let n = list.length
        let middle = n/2
        return merge(mergesort(list.slice(0, middle)), mergesort(list.slice(middle, n)))
    }
}

function merge(listA, listB){
    let list = []

    listA.push(Infinity)
    listB.push(Infinity)

    let i = 0
    let j = 0

    while(i < listA.length-1 || j < listB.length-1){
        if(listA[i] < listB[j]){
            list.push(listA[i])
            i++
        }else{
            list.push(listB[j])
            j++
        }
    }

    return list

}

Do you have any idea of how can I improve this?

\$\endgroup\$
  • 1
    \$\begingroup\$ I've edited the title so it doesn't imply that you think it might not work. HTH. \$\endgroup\$ – Toby Speight Aug 14 at 10:31
  • \$\begingroup\$ I guess you can always nitpick and find little mistakes to improve, but I don't see a way to substantially improve this code, \$\endgroup\$ – Shahrukh Haider Aug 14 at 12:14
  • \$\begingroup\$ Why do you add 'Infinity' to both lists in the merge function? \$\endgroup\$ – dustytrash Aug 14 at 13:15
  • \$\begingroup\$ I add infinity because if you short 1 > undefined, and if the array is empty when you try to get access you only get undefined, so the sort process fail \$\endgroup\$ – Es-Loop Aug 14 at 13:36
  • \$\begingroup\$ if(list.length < 2) ... else if(list.length > 1) ... You can turn the else if into just an else since all lists have a length bigger than 1 if they are not less than 2 big. \$\endgroup\$ – spyr03 Aug 14 at 13:59
3
\$\begingroup\$

I don't see a way to improve the algorithm, but here are some general coding tips:

A number can either be greater than 1, or less than 2. So you can use 'else' here instead.

if(list.length < 2){
    return list
}else if(list.length > 1){

Sometimes people create extra variables to improve readability, but here 'n' is less readable than list.length.

let n = list.length

A little bit of commenting can go a long way, for example if you could explain why you add 'Infinity' to the lists in a comment:

listA.push(Infinity)
listB.push(Infinity)
\$\endgroup\$
2
\$\begingroup\$
  • The most valuable property of merge sort is stability: the elements compared equal retain their relative order. The condition

        if(listA[i] < listB[j]){
    

    destabilizes. If the elements happen to be equal, one from listB will be merged first. A simple fix is to rewrite the condition as

        if(listB[i] < listA[j]){
    
  • The Infinity trick assumes that there is no legitimate Infinity in the original data. If there are, the code may fail. Consider a case in which listA ends with the legitimate one. Then the listB will be accessed out-of-bounds.

\$\endgroup\$
  • \$\begingroup\$ I cannot understand your first point, if the sort is from least to greatest, the idea is that you can get an object of the listA first, so if the two elements are the same, you will get the element from the listB, but i think that this is not important, can you put an example? thanks \$\endgroup\$ – Tlaloc-ES Aug 14 at 21:09
  • \$\begingroup\$ And the point two if in the list there are other infinity this is not a problem because the while condition is i < listA.length-1 can you put another example of this? \$\endgroup\$ – Tlaloc-ES Aug 14 at 21:12
  • \$\begingroup\$ I tested the function with: console.log(mergesort([2,1])) console.log(mergesort([5,4,3])) console.log(mergesort([5,1,3,2,6,9])) console.log(mergesort([5,1,3,2,6,9,10])) console.log(mergesort([1,2])) console.log(mergesort([3,4,5])) console.log(mergesort([1,2,4,4,5,6,7,8])) console.log(mergesort([1,2,3,4,5,6,7,8,9])) \$\endgroup\$ – Tlaloc-ES Aug 14 at 21:12
  • 2
    \$\begingroup\$ @Tlaloc-ES Re first point: try to sort something more interesting than integers. E.g. records {firstname, lastname}. Make 2 runs: sort by first name, then sort the sorted list by last name. If the algorithm is stable, you will get people sorted correctly. Otherwise, the first names of the same last name end up in a disarray. \$\endgroup\$ – vnp Aug 14 at 21:19
  • 1
    \$\begingroup\$ @Tlaloc-ES Re second point, try to merge listA = {Infinity, Infinity} with listB = {0, 1}. \$\endgroup\$ – vnp Aug 14 at 21:20
2
\$\begingroup\$

You are not sorting in place - that is: the input array is untouched by the operation and you return a new sorted array. I would expect the input array to be sorted when the function returns. Javascript's Array.sort() behaves this way.


listA.push(Infinity)
listB.push(Infinity)

I you encounter a problem where you are tempted to do this, you should definitely reconsider your approach.

Instead you could do:

function merge(listA, listB) {
  let list = []
  let i = 0
  let j = 0

  while (i < listA.length && j < listB.length) {
    if (listA[i] < listB[j]) {
      list.push(listA[i])
      i++
    } else {
      list.push(listB[j])
      j++
    }
  }

  while (i < listA.length)
    list.push(listA[i++]);
  while (j < listB.length)
    list.push(listB[j++]);

  return list;
}

or:

function merge(listA, listB) {
  let list = []

  let i = 0
  let j = 0

  while (i < listA.length || j < listB.length) {
    if (i < listA.length && (listA[i] < listB[j] || j >= listB.length)) {
      list.push(listA[i])
      i++
    } else {
      list.push(listB[j])
      j++
    }
  }

  return list;
}
\$\endgroup\$
1
\$\begingroup\$

Readability Review

It is fine to use n to represent a count or size. It's a variable name common in mathematics, and in expansion also when programming algorithms. However, OP mixes list.length and n representing the same thing, this is bad practice as it's confusing. Furthermore:

  • I would use const over let if a variable is immutable.
  • Include sufficient white space between operators and member declarations for readability
  • Add semicolon as statement separator
  • Get rid of redundant else if statements. Since we exit early, even an else is not required.
  • Inline an if statement if it's compact. This saves you lines without losing readability.
  • A 4 char indentation is ok, but I would prefer 2 for javascript.
function mergesort (list) {
  const n = list.length;
  if (n < 2) return list;
  const middle = n / 2;
  return merge(mergesort(list.slice(0, middle)), mergesort(list.slice(middle, n)));
}

as compared to..

function mergesort(list){
    if(list.length < 2){
        return list
    }else if(list.length > 1){
        let n = list.length
        let middle = n/2
        return merge(mergesort(list.slice(0, middle)), mergesort(list.slice(middle, n)))
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.