JavaScript Coding Test Course, Merge Sort

Hello! In this blog post, we will discuss the Merge Sort algorithm to help you prepare for JavaScript coding tests. Merge Sort is one of the most widely used sorting algorithms, with a time complexity of O(n log n) and excellent performance. In this post, we will dramatically explain the concept of Merge Sort, how it works, its implementation in JavaScript, and practical use cases in coding tests.

What is Merge Sort?

Merge Sort is an algorithm that uses the divide and conquer method. The basic idea of this algorithm is to recursively divide the array into two sub-arrays, sort each of the sub-arrays, and then merge these two sub-arrays into one sorted array. Merge Sort goes through the following steps:

  • Divide the array into two sub-arrays based on a midpoint.
  • Recursively sort each sub-array.
  • Merge the two sorted sub-arrays to finally create one sorted array.

The Process of Merge Sort

Let’s take a closer look at how Merge Sort works using an example. Suppose we have an array to sort: [38, 27, 43, 3, 9, 82, 10].

Step 1: Splitting the Array

First, let’s divide the array based on the midpoint. This array can be split into the following two sub-arrays:

  • [38, 27, 43]
  • [3, 9, 82, 10]

Step 2: Recursive Sorting

Now, we repeat the same process for each sub-array. Continuing to split:

  • [38, 27] -> [38] and [27]
  • [3, 9, 82, 10] -> [3, 9] and [82, 10] -> [3] and [9], [82] and [10]

Step 3: Merging After Sorting

Now that each sub-array has been split into single elements, let’s merge them back while sorting:

  • Merge [38] and [27] to get [27, 38]
  • Merge [3] and [9] to get [3, 9]
  • Merge [82] and [10] to get [10, 82]

Now that we have the sorted sub-arrays, let’s merge them again:

  • Merge [27, 38] and [3, 9] to get [3, 9, 27, 38]
  • Merge [3, 9, 27, 38] and [10, 82] to get [3, 9, 10, 27, 38, 82]

The final sorted array is [3, 9, 10, 27, 38, 82].

Time Complexity Analysis of Merge Sort

The time complexity of Merge Sort is O(n log n). This results from the combination of two factors:

  • In the process of dividing the array, the size of the array decreases by half, resulting in log n stages.
  • At each stage, merging the two sub-arrays takes O(n) time.

As a result, Merge Sort is widely used as a stable sorting method. However, it has the drawback of relatively high memory usage.

Implementing Merge Sort in JavaScript

Now, let’s implement Merge Sort in JavaScript. Merge Sort fundamentally uses a recursive function. Below is the JavaScript code:

        
function mergeSort(arr) {
    if (arr.length <= 1) {
        return arr; // Base case: return the array as is when it has one element
    }

    const mid = Math.floor(arr.length / 2); // Mid index of the array
    const left = mergeSort(arr.slice(0, mid)); // Recursively sort the left part
    const right = mergeSort(arr.slice(mid)); // Recursively sort the right part

    return merge(left, right); // Merge the two sorted parts
}

function merge(left, right) {
    const sortedArray = [];
    let leftIndex = 0; // Left array index
    let rightIndex = 0; // Right array index

    // Repeat while neither of the arrays is empty
    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] < right[rightIndex]) {
            sortedArray.push(left[leftIndex]); // Add the smaller element from the left
            leftIndex++;
        } else {
            sortedArray.push(right[rightIndex]); // Add the smaller element from the right
            rightIndex++;
        }
    }

    // Add any remaining elements
    return sortedArray.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

// Test
const array = [38, 27, 43, 3, 9, 82, 10];
const sortedArray = mergeSort(array);
console.log(sortedArray); // Output: [3, 9, 10, 27, 38, 43, 82]

Applications and Cautions of Merge Sort

Merge Sort is most commonly used when there is a need to sort a large amount of data. It is particularly useful in external sorting (e.g., sorting files). Since Merge Sort is a stable sorting algorithm, it is suitable for cases where the original order must be preserved. However, it consumes a significant amount of memory, so in memory-constrained environments, other algorithms may need to be considered.

Conclusion

In this post, we have learned about Merge Sort in detail. From the basic concepts of the algorithm to its implementation, we covered content that can be useful in coding tests. If you can understand and implement Merge Sort well, you will have a solid foundation to easily acquire other algorithms as well. I hope this helps you in your coding test preparation, and I will return with more useful information in the next post. Thank you!