Lesson 5

Hello, rookie coders!

Today, we are focusing on the mighty **Merge Sort**, a potent way to organize data. It's time to explore and code this technique in **JavaScript**. Imagine shuffling a deck of cards and then rearranging them in order. Merge Sort accomplishes exactly this with data, but on a grander scale, making it top-tier for large-scale data.

First, let's build a `merge()`

function in JavaScript. It merges two sorted arrays into a single sorted array. Think of it as combining two sorted stacks of cards into one sorted stack.

JavaScript`1function merge(left, right) { 2 let resultArray = [], leftIndex = 0, rightIndex = 0; 3 4 // sorting and merging process 5 while(leftIndex < left.length && rightIndex < right.length) { 6 if(left[leftIndex] < right[rightIndex]) { 7 resultArray.push(left[leftIndex]); // the smaller of the two elements is added to the result array 8 leftIndex++; // move to the next element in the left array 9 } else { 10 resultArray.push(right[rightIndex]); // same as above but with the right array 11 rightIndex++; 12 } 13 } 14 15 // Return the sorted array 16 return resultArray 17 .concat(left.slice(leftIndex)) 18 .concat(right.slice(rightIndex)); 19}`

The `merge()`

function above takes two sorted arrays (`left`

and `right`

) and combines them into one sorted array (`resultArray`

).

Seemingly tricky, the code is very straightforward:

- We place two pointers,
`leftIndex`

and`rightIndex`

, at the beginning of the`left`

and`right`

arrays. - We choose the smaller element, put it in the final array
`resultArray`

, and move the corresponding pointer further. - We keep doing this until one of the pointers reaches the end of its array.

We stop the process when one of the pointers reaches the end of its array, but some elements could be left in the other array.

To handle this, we copy the remaining elements of both arrays (if any) to the end of the resulting `arr`

array, using `.concat`

method.

Next, we'll implement the complete Merge Sort algorithm in JavaScript. This process involves splitting an array into halves until we reach an array containing only one element. Arrays of one element are naturally sorted so that we can merge them into one sorted array. Then, we can merge the obtained arrays of two elements. This process goes until we merge all arrays into one sorted array.

JavaScript`1function mergeSort (unsortedArray) { 2 if (unsortedArray.length <= 1) { 3 return unsortedArray; // If the array has only one element, it's already sorted 4 } 5 6 const middle = Math.floor(unsortedArray.length / 2); // This will get the midpoint of the array 7 const left = unsortedArray.slice(0, middle); // We split the array into two halves 8 const right = unsortedArray.slice(middle); // This is the right half 9 10 // Merge the two halves back together 11 return merge( 12 mergeSort(left), mergeSort(right) 13 ); 14}`

**Voila!** You've successfully decoded the Merge Sort algorithm in JavaScript!

Merge Sort is consistent in performance, making it reliable. Merge Sort has impressive time complexity of **O(n log n)**. This makes it a top contender when sorting large datasets! However, it does use extra memory during the merge process. Think of this as sorting a deck of cards: you need space to spread them out before shuffling them back together.

Well done! You've mastered the theory of the Merge Sort algorithm in JavaScript. Understanding its pros and cons and the **O(n log n)** time complexity is extremely valuable.

As we navigate toward practical challenges, expect hands-on practice and the opportunity to delve into the magic of the Merge Sort algorithm in solving engaging coding problems! Let's jump right into our coding universe!