Merge Sort Algorithm in DSA Javascript - Build from Scratch

Merge Sort Algorithm

📖 Scenario: Imagine you are organizing a list of numbers to prepare for a game where numbers must be in order. You want to use a smart way to sort the numbers quickly and correctly.

🎯 Goal: You will build the Merge Sort algorithm step-by-step in JavaScript. This algorithm splits the list into smaller parts, sorts them, and then joins them back together in order.

📋 What You'll Learn

Create an array called numbers with the exact values: [38, 27, 43, 3, 9, 82, 10]

Create a helper function called merge that takes two sorted arrays and returns one sorted array

Create a recursive function called mergeSort that splits the array and uses merge to sort and combine

Print the sorted array returned by mergeSort(numbers)

💡 Why This Matters

🌍 Real World

Merge Sort is used in many software systems to sort large lists efficiently, such as sorting user data, search results, or organizing files.

💼 Career

Understanding Merge Sort helps in technical interviews and improves problem-solving skills for software development roles.

1

Create the initial array

Create an array called numbers with these exact values: [38, 27, 43, 3, 9, 82, 10]

DSA Javascript

// Create the array 'numbers' with the given values
// Your code here

Hint

Use const numbers = [38, 27, 43, 3, 9, 82, 10]; to create the array.

2

Create the merge function

Create a function called merge that takes two sorted arrays named left and right and returns one sorted array by comparing elements from both arrays.

DSA Javascript

const numbers = [38, 27, 43, 3, 9, 82, 10];

// Create the merge function below
// Your code here

Hint

Use two pointers to compare elements from left and right arrays and build a sorted result array.

3

Create the mergeSort function

Create a recursive function called mergeSort that takes an array arr. If the array length is 1 or less, return it. Otherwise, split the array into two halves, call mergeSort on each half, and return the result of calling merge on the two sorted halves.

DSA Javascript

const numbers = [38, 27, 43, 3, 9, 82, 10];

function merge(left, right) {
    let result = [];
    let i = 0;
    let j = 0;

    while (i < left.length && j < right.length) {
        if (left[i] < right[j]) {
            result.push(left[i]);
            i++;
        } else {
            result.push(right[j]);
            j++;
        }
    }

    return result.concat(left.slice(i)).concat(right.slice(j));
}

// Create the mergeSort function below
// Your code here

Hint

Split the array into two halves, sort each half by calling mergeSort recursively, then merge the sorted halves.

4

Print the sorted array

Print the sorted array by calling console.log(mergeSort(numbers)).

DSA Javascript

const numbers = [38, 27, 43, 3, 9, 82, 10];

function merge(left, right) {
    let result = [];
    let i = 0;
    let j = 0;

    while (i < left.length && j < right.length) {
        if (left[i] < right[j]) {
            result.push(left[i]);
            i++;
        } else {
            result.push(right[j]);
            j++;
        }
    }

    return result.concat(left.slice(i)).concat(right.slice(j));
}

function mergeSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }

    const middle = Math.floor(arr.length / 2);
    const left = arr.slice(0, middle);
    const right = arr.slice(middle);

    return merge(mergeSort(left), mergeSort(right));
}

// Print the sorted array below
// Your code here

Hint

Use console.log(mergeSort(numbers)) to print the sorted array.