step 1 - setting up js codeStep 2 -building mergesort functionSTEP 3 - working with merge functionStep 3 - filtering arrays |
We need to set up two functions
We have an array and we need to split it into 2. It's no problem when you have even number of elements in the array but we need to be able to take into consideration what if the number of elements is odd. Math.floor() function comes handy. Math.floor() returns the largest integer less than or equal to a given number. So let's say, 5/2 should be 2.5, with Math.Floor() invoked, you get 2.
Now, we assign 1st half of the array to var firstHalf. We need to introduce a slice because we are splitting an array.
Looks good. Now, we have a little problem. What if our array contains either 0 or 1 element. We need if statement
We need to add return statement inside of mergeSort function basically we are merging both firstHalf and secondHalf together. That return statement introduces us to merge function.
Now, in function merge (array1, array2) {} we will compare each element inside of both arrays with each other and sort them, and a element with a lesser value into a final array where an entire new sorted array will be stored.
The very next thing we need to do is add while loop. We want to sort through both arrays at the same time. In simple English, while both arrays are not empty sort both arrays into one. :)
As I mentioned earlier. Inside of the while look, we will take the smallest value of the array and shift it into a position inside of the var result array. The very last thing we need to add inside of the merge function is take results from minElem and add them into a variable result
This looks good! BUT there is one problem.
Let me illustrate the problem. For example, array1 = [2,6,9,10,12] & array2 = [1, 7, 29, 11] result array is [1, 2, 6, 7, 9, 10, 11, 12]. We are left with 29 inside of array2. We have nothing 29 to compare to. We need another if statement. All you need to do is run the algorithm.
console.log(mergeSort([90, 33, 11, 3, 32, 12, 1, 0])); Your output should be [0, 1, 3, 11, 12, 32, 33, 90] |