Data Structure Merge Sort Practice Questions with Solutions

By /

Introduction

Merge Sort is a powerful sorting algorithm based on the divide-and-conquer approach. It repeatedly divides an array into smaller parts, sorts those parts, and then merges them into one sorted array. In this chapter, you will practice Merge Sort using JavaScript through 10 solved questions covering ascending and descending order, merge operations, recursion, duplicate values, strings, objects, and reusable functions. Data Structure Merge Sort practice questions with solutions help to understand the concepts.

Question 1: Sort an Array Using Merge Sort

Question

Sort the following array in ascending order using Merge Sort:

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

Solution

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

    let mid = Math.floor(arr.length / 2);

    let left = mergeSort(arr.slice(0, mid));
    let right = mergeSort(arr.slice(mid));

    return merge(left, right);
}

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++;
        }
    }

    while (i < left.length) {
        result.push(left[i]);
        i++;
    }

    while (j < right.length) {
        result.push(right[j]);
        j++;
    }

    return result;
}

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

console.log(mergeSort(numbers));

Output

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

Question 2: Understand How Merge Sort Divides an Array

Question

What smaller arrays are created when Merge Sort processes:

let numbers = [8, 4, 7, 3, 6, 2, 5, 1];

Solution

Merge Sort first divides the array into two halves:

[8, 4, 7, 3]    [6, 2, 5, 1]

Then each half is divided again:

[8, 4] [7, 3]    [6, 2] [5, 1]

Finally:

[8] [4] [7] [3] [6] [2] [5] [1]

Now the individual elements are merged in sorted order.

For example:

[8] + [4] → [4, 8]

[7] + [3] → [3, 7]

[6] + [2] → [2, 6]

[5] + [1] → [1, 5]

Then:

[4, 8] + [3, 7] → [3, 4, 7, 8]

[2, 6] + [1, 5] → [1, 2, 5, 6]

Finally:

[3, 4, 7, 8] + [1, 2, 5, 6]

becomes:

[1, 2, 3, 4, 5, 6, 7, 8]

Output

[1, 2, 3, 4, 5, 6, 7, 8]

Question 3: Sort an Array in Descending Order

Question

Use Merge Sort to arrange the following array from largest to smallest:

let numbers = [12, 5, 19, 7, 2, 15];

Solution

Change the comparison inside the merge function so that the larger value is selected first.

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

    let mid = Math.floor(arr.length / 2);

    let left = mergeSort(arr.slice(0, mid));
    let right = mergeSort(arr.slice(mid));

    return merge(left, right);
}

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++;
        }
    }

    while (i < left.length) {
        result.push(left[i]);
        i++;
    }

    while (j < right.length) {
        result.push(right[j]);
        j++;
    }

    return result;
}

let numbers = [12, 5, 19, 7, 2, 15];

console.log(mergeSort(numbers));

Output

[19, 15, 12, 7, 5, 2]

Question 4: Merge Two Already Sorted Arrays

Question

Merge these two sorted arrays into one sorted array:

let left = [2, 6, 10, 14];
let right = [1, 5, 8, 12];

Solution

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++;
        }
    }

    while (i < left.length) {
        result.push(left[i]);
        i++;
    }

    while (j < right.length) {
        result.push(right[j]);
        j++;
    }

    return result;
}

let left = [2, 6, 10, 14];
let right = [1, 5, 8, 12];

console.log(merge(left, right));

Output

[1, 2, 5, 6, 8, 10, 12, 14]

Question 5: Count the Number of Merge Operations

Question

For an array containing 8 elements, how many merge operations are performed during a complete Merge Sort?

Solution

For 8 elements, the division looks like this:

8
↓
4 + 4
↓
2 + 2 + 2 + 2
↓
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

After reaching individual elements, the merging happens in levels.

First merge level:

4 merges

Second merge level:

2 merges

Final merge level:

1 merge

Total:

4 + 2 + 1 = 7

Output

7 merge operations

For n elements, Merge Sort performs approximately n - 1 merge operations when considering the complete binary merge tree.

Question 6: Sort an Array Containing Duplicate Values

Question

Sort the following array using Merge Sort:

let numbers = [7, 3, 7, 2, 3, 9, 2];

Solution

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

    let mid = Math.floor(arr.length / 2);

    let left = mergeSort(arr.slice(0, mid));
    let right = mergeSort(arr.slice(mid));

    return merge(left, right);
}

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++;
        }
    }

    while (i < left.length) {
        result.push(left[i]);
        i++;
    }

    while (j < right.length) {
        result.push(right[j]);
        j++;
    }

    return result;
}

let numbers = [7, 3, 7, 2, 3, 9, 2];

console.log(mergeSort(numbers));

Output

[2, 2, 3, 3, 7, 7, 9]

Notice that Merge Sort does not remove duplicate values. It only rearranges them.

Question 7: Sort Strings Using Merge Sort

Question

Sort the following strings alphabetically using Merge Sort:

let names = ["Ravi", "Aman", "Karan", "Neha", "Priya"];

Solution

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

    let mid = Math.floor(arr.length / 2);

    let left = mergeSort(arr.slice(0, mid));
    let right = mergeSort(arr.slice(mid));

    return merge(left, right);
}

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

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

    while (i < left.length) {
        result.push(left[i]);
        i++;
    }

    while (j < right.length) {
        result.push(right[j]);
        j++;
    }

    return result;
}

let names = ["Ravi", "Aman", "Karan", "Neha", "Priya"];

console.log(mergeSort(names));

Output

["Aman", "Karan", "Neha", "Priya", "Ravi"]

Question 8: Sort Students by Marks Using Merge Sort

Question

Sort these students from highest marks to lowest marks using Merge Sort:

let students = [
    { name: "Aman", marks: 72 },
    { name: "Riya", marks: 91 },
    { name: "Karan", marks: 85 },
    { name: "Neha", marks: 78 }
];

Solution

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

    let mid = Math.floor(arr.length / 2);

    let left = mergeSort(arr.slice(0, mid));
    let right = mergeSort(arr.slice(mid));

    return merge(left, right);
}

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

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

    while (i < left.length) {
        result.push(left[i]);
        i++;
    }

    while (j < right.length) {
        result.push(right[j]);
        j++;
    }

    return result;
}

let students = [
    { name: "Aman", marks: 72 },
    { name: "Riya", marks: 91 },
    { name: "Karan", marks: 85 },
    { name: "Neha", marks: 78 }
];

console.log(mergeSort(students));

Output

[
    { name: "Riya", marks: 91 },
    { name: "Karan", marks: 85 },
    { name: "Neha", marks: 78 },
    { name: "Aman", marks: 72 }
]

Question 9: Count Comparisons During Merge Sort

Question

Write a Merge Sort program that counts how many element comparisons are made while sorting:

[10, 4, 7, 2]

Solution

let comparisons = 0;

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

    let mid = Math.floor(arr.length / 2);

    let left = mergeSort(arr.slice(0, mid));
    let right = mergeSort(arr.slice(mid));

    return merge(left, right);
}

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

    while (i < left.length && j < right.length) {
        comparisons++;

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

    while (i < left.length) {
        result.push(left[i]);
        i++;
    }

    while (j < right.length) {
        result.push(right[j]);
        j++;
    }

    return result;
}

let numbers = [10, 4, 7, 2];

let sorted = mergeSort(numbers);

console.log(sorted);
console.log("Comparisons:", comparisons);

Output

[2, 4, 7, 10]
Comparisons: 5

The comparison counter increases whenever the algorithm compares the current elements of the two sorted halves.

Question 10: Create a Reusable Merge Sort Function

Question

Create a reusable Merge Sort function that can sort different numeric arrays.

Test it with:

[25, 10, 30, 15, 5]

and

[42, 17, 8, 99, 23, 1]

Solution

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

    let mid = Math.floor(arr.length / 2);

    let left = mergeSort(arr.slice(0, mid));
    let right = mergeSort(arr.slice(mid));

    return merge(left, right);
}

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), right.slice(j));
}

let numbers1 = [25, 10, 30, 15, 5];
let numbers2 = [42, 17, 8, 99, 23, 1];

console.log(mergeSort(numbers1));
console.log(mergeSort(numbers2));

Output

[5, 10, 15, 25, 30]
[1, 8, 17, 23, 42, 99]

The same function can now be reused with different numeric arrays.

Key Takeaways

  • Merge Sort uses the divide-and-conquer technique.
  • The array is repeatedly divided into smaller parts.
  • Individual elements are eventually merged back together.
  • During merging, elements are placed in the correct order.
  • Merge Sort can sort numbers, strings, and objects.
  • Duplicate values are preserved.
  • Changing the comparison allows ascending or descending sorting.
  • The standard time complexity of Merge Sort is O(n log n).
  • Merge Sort generally requires O(n) additional space for the merging process.
  • Merge Sort is especially useful when predictable sorting performance is important.
  • The recursive mergeSort() function handles division.
  • The merge() function combines two sorted arrays.

FAQs

1. What is Merge Sort in Data Structures?

Merge Sort is a sorting algorithm that divides an array into smaller parts, sorts those parts, and then merges them to produce a sorted array.

2. What technique does Merge Sort use?

Merge Sort uses the divide-and-conquer technique.

3. What is the time complexity of Merge Sort?

Merge Sort has a time complexity of O(n log n) in the best, average, and worst cases.

4. Does Merge Sort work with duplicate values?

Yes. Merge Sort preserves duplicate values while arranging the elements in sorted order.

5. Can Merge Sort sort strings?

Yes. By changing the comparison logic, Merge Sort can alphabetically sort strings.

6. Can Merge Sort sort objects?

Yes. You can compare a specific property of an object, such as marks, price, age, or salary, and sort the objects based on that property.

7. How much extra space does Merge Sort require?

The common array-based implementation requires O(n) additional space for temporary arrays used during merging.

Written by Shubhranshu Shekhar, who has trained 20000+ students in coding.

Related Posts

Scroll to Top