How to efficiently sort a large array

A buddy of mine from up in Canada is in the same full-stack group as me. He happened to be out for a little while, and needed to get caught up on the course work. I had a very fun time explaining merge sorts over the phone, and surprisingly...we did not need to get on for a zoom call. I guess the more you understand something, the easier it is to explain it. Just a fair warning....this is not exactly my own original code but thought this would be a good example to explain, and this was something we came up with in my group together.

Firstly, what is a merge sort algorithm used for? Its used to simply sort a very large array. You could use a simple linear sort but you are talking about possibly longer processing time if you are trying to cover a very large array. In comes the merge sort algorithm meteor.

For the sake of just showing how this works, I am just going to use a small array...no need to get crazy.

const someArray = [10,5,19,18,6,11,13]

There are actually two parts to this, there is a function that will mergeSort function, and there is a merge function

const mergeSort = (array)=>{}

const merge =(left,right)=>{}

I will start building up the mergeSort function then move to the merge function.

function mergeSort(array) {
//#1  
const half = array.length / 2 

  //#2
  if(array.length < 2){ 
    return array 
  }

  //#3
  const left = array.splice(0, half) 
  //#4
  return merge(mergeSort(left),mergeSort(array))
  //
}

So since there are no line numbers, I thought it was best I left some number labels in the code above to help you follow along

1) The array passed in will get chopped in half into two sub arrays

2) If the array is less than the length of 2, the array just gets returned ending it right here

3) the left array will start from 1st index up to where the half variable starts

4) the split array is now passed into the returned merge function as the left and right parameters

Now what is going on in the mysterious merge function?

 //#1
 let arr = []

 //#2   
while (left.length && right.length) {
        // Pick the smaller among the smallest element of left and 
//#3
right sub arrays 
        if (left[0] < right[0]) {
            arr.push(left.shift())  
        } else {
            arr.push(right.shift()) 
        }
    }

  //#4

    return [ ...arr, ...left, ...right ]

1) an empty array is setup

2) Both the left and right array have to have elements in them at the same time for this loop to work

3) The first element values in both arrays are being compared to see which is the smallest. The smallest will get pushed in the empty array we sat up in the beginning of the function. One thing you will need to keep in mind the first index values are getting updated in each array as they are leaving the sub arrays, hence why we are always comparing the first index

4) So..there was one thing I didn't mention..In some cases there will be an array that has odd number of indexes. When split the array in the mergeSort function typically that left over index goes in you first sub array. At label #4 the while loop is over because only one sub array has a value and is just concatenated to the back of the array that all the other values were getting pushed into earlier

When all of this processes, our array in the beginning results to this output:

5,6,10,11,13,18,19

I hope this was enlightening as I found. Any feedback is appreciated if you find anything wrong with this. Have a great evening folks!

Here is the full code:

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

    while (left.length && right.length) {
        right sub arrays 
        if (left[0] < right[0]) {
            arr.push(left.shift())  
        } else {
            arr.push(right.shift()) 
        }
    }


    return [ ...arr, ...left, ...right ]
}
function mergeSort(array) {
  const half = array.length / 2


  if(array.length < 2){
    return array 
  }

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

Comments

[Christian Herlein]

Nice post, congrats!

Anyways, despite mergesort is a good algorithm, js's v8 engine implements timesort, wich is an improvement on mergesort. That results on Array#sort faster than a dev side algorithm.

Try its performance with large (or growing) inputs and compare it against -for example- inputs.sort((n1, n2) => ((n1 - n2) / Math.abs((n1 - n2))) | 0 )

That said... it's a really good explanation on sorting.

Cheers!

[birowo]

you mean timsort : v8.dev/blog/array-sort#timsort

[Curtis Laurence Chadwell]

I will have to look into this! Thank you by the way for the support!