Merge Sort MCQ Quiz - Objective Question with Answer for Merge Sort - Download Free PDF

Merge sort 

It is based on the divide and conquers approach.

Recurrence relation for merge sort will become:

T(n) = 2T (n/2) + Θ (n)

Using Master’s theorem

T (n) = n × log₂n

Therefore, the time complexity of Merge Sort is θ(nlogn).

Binary Search

Search a sorted array by repeatedly dividing the search interval in half.

Recurrence for binary search is T(n) = T(n/2) + θ(1)

Using Master’s theorem

T (n) = log₂n

Consider only half of the input list and throw out the other half. Hence time complexity is O(log n).

The correct answer is Divide and Conquer.

Key Points

• Merge Sort is an efficient, stable, and comparison-based sorting algorithm.
• It follows the Divide and Conquer paradigm, which means it divides the array into smaller subarrays, sorts those subarrays, and then merges them back together to form the sorted array.
• The algorithm recursively divides the array into two halves until each subarray contains a single element or no elements (base case).
• After dividing the array, it then merges the subarrays in a sorted manner to produce the final sorted array.
• The time complexity of Merge Sort is O(n log n), making it very efficient for large datasets.

Additional Information

• Merge Sort is a stable sort, meaning that it preserves the relative order of equal elements.
• It is also an out-of-place sort as it requires additional space proportional to the size of the input array.
• Because of its consistent O(n log n) time complexity, it performs well on large datasets and is used in various applications.
• Merge Sort is especially useful for linked lists and external sorting (where data doesn't fit into memory).

The correct answer is option 1.

Concept:

Merge-sort algorithm:

Merge Sort is a Divide and Conquer algorithm. It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves.

The merge() function is used for merging two halves. The merge(arr, l, m, r) is a key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one.

Algorithm:

MergeSort(arr[ ], l,  r)

If r > l

• Find the middle point to divide the array into two halves: middle m = l+ (r-l)/2
• Call mergeSort for first half: Call mergeSort(arr, l, m)
• Call mergeSort for second half: Call mergeSort(arr, m+1, r)
• Merge the two halves sorted in steps 2 and 3: Call merge(arr, l, m, r)

Time complexity:

Sorting arrays on different machines. Merge Sort is a recursive algorithm and time complexity can be expressed as following recurrence relation.

T(n) = 2T(n/2) + θ(n)

Worst case= Θ(n lg n)

Best case= Θ(n lg n)

Average case= Θ(n lg n)

Hence the correct answer is Θ(n lg n).

The correct answer is option 1.

Concept:

Merge-sort algorithm:

Merge Sort is a Divide and Conquer algorithm. It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves.

The merge() function is used for merging two halves. The merge(arr, l, m, r) is a key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one.

Algorithm:

MergeSort(arr[ ], l,  r)

If r > l

• Find the middle point to divide the array into two halves: middle m = l+ (r-l)/2
• Call mergeSort for first half: Call mergeSort(arr, l, m)
• Call mergeSort for second half: Call mergeSort(arr, m+1, r)
• Merge the two halves sorted in steps 2 and 3: Call merge(arr, l, m, r)

Time complexity:

Sorting arrays on different machines. Merge Sort is a recursive algorithm and time complexity can be expressed as following recurrence relation.

T(n) = 2T(n/2) + θ(n)

Worst case= Θ(n lg n)

Best case= Θ(n lg n)

Average case= Θ(n lg n)

Hence the correct answer is Θ(n lg n).

Option_1: Insertion Sort

In Insertion sort, if the array is already sorted, then it takes O(n) time and if it is sorted is decreasing order, then it takes O(n²) time to sort the array.

Option_2: Quick Sort

In Quick sort, if the array is already sorted whether in decreasing or in non-decreasing order, then it takes O(n²) time.

Option_3 – Merge Sort

Merge sort gives time complexity of O(nlogn) in every case, be it best, average or worst. In merge sort, performance is affected least by the order of input sequence.

Option_4: Selection Sort

Given sequence: 20, 24, 30, 35, 50

Ascending order: 20, 24, 30, 35, 50

Merge(20, 24) → new size (44)

Number of comparisons = 20 + 24 – 1 = 43  

Sequence: 30, 35, 44, 50

Merge(30, 35) → new size (65)

Number of comparisons = 30 + 35 – 1 = 64  

Sequence:  44, 50, 65

Merge(44, 50) → new size (94)

Number of comparisons = 44 + 50 – 1 = 93

Sequence:  65, 94

Merge(65, 94) → new size (150)

Number of comparisons = 65 + 94 – 1 = 158  

Option_1: Insertion Sort

In Insertion sort, if the array is already sorted, then it takes O(n) time and if it is sorted is decreasing order, then it takes O(n²) time to sort the array.

Option_2: Quick Sort

In Quick sort, if the array is already sorted whether in decreasing or in non-decreasing order, then it takes O(n²) time.

Option_3 – Merge Sort

Merge sort gives time complexity of O(nlogn) in every case, be it best, average or worst. In merge sort, performance is affected least by the order of input sequence.

Option_4: Selection Sort

Concept:

Merge sort algorithm worst case time complexity is O (nlogn)

Data:

T₁ (n) =30 seconds, n₁ = 64

T₂ (n) = 6 minutes

Formula:

T(n) = nlog₂n

Calculation:

30 = c × 64 log₂(64)

30 = c × 64 log₂(2⁶)

30 = c × 64 × 6

\(c = \frac{5}{{64}}\)

6 × 30 = c n₂ log₂n₂

\(6 \times 60 = \frac{5}{{64}} \times {n_2}{\log _2}{n_2}\)

∴ n₂ = 512

The correct answer is option 1.

Concept:

Merge-sort algorithm:

Merge Sort is a Divide and Conquer algorithm. It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves.

The merge() function is used for merging two halves. The merge(arr, l, m, r) is a key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one.

Algorithm:

MergeSort(arr[ ], l,  r)

If r > l

• Find the middle point to divide the array into two halves: middle m = l+ (r-l)/2
• Call mergeSort for first half: Call mergeSort(arr, l, m)
• Call mergeSort for second half: Call mergeSort(arr, m+1, r)
• Merge the two halves sorted in steps 2 and 3: Call merge(arr, l, m, r)

Time complexity:

Sorting arrays on different machines. Merge Sort is a recursive algorithm and time complexity can be expressed as following recurrence relation.

T(n) = 2T(n/2) + θ(n)

Worst case= Θ(n lg n)

Best case= Θ(n lg n)

Average case= Θ(n lg n)

Hence the correct answer is Θ(n lg n).

• Merge sort is an efficient sorting algorithm that uses a divide-and-conquer approach to order elements in an array.
• Mergesort has two steps:
  • Merging
  • Sorting.

• The algorithm uses a divide-and-conquer approach to merge and sort a list.

The recursive mergesort algorithm is

1. If the list has only one element, Return the list and terminate. (Base case)

2. Split the list into two halves that are as equal in length as possible. (Divide)

3. Using recursion, sort both lists using mergesort. (Conquer)

4. Merge the two sorted lists and return the result. (Combine)

The correct answer is option 2.

Key Points

• Two-way merge sort algorithm to sort the following elements in ascending order 20, 47, 15, 8, 9, 4, 40, 30, 12, 17 

Hence, after the 2nd pass list would be  8, 15, 20, 47, 4, 9, 30 40, 12, 17 

Additional Information

•  Sorting arrays through several computers. Merge Sort is a recursive algorithm with the following recurrence relation for time complexity.
• T(n) = 2T(n/2) + θ(n)
• Time complexity two-way merge sort is O(N log N)
• complete merge sort process for an example array {38, 27, 43, 3, 9, 82, 10}

Merge sort:

Merge sort complexity is independent of the distribution of data. Merge sort is based on the divide and conquer approach. Recurrence relation for merge sort will become:

T(n) = 2T (n/2) + Θ (n)

T(n) = n + Θ (n)

T (n) = n × logn

Merge sorting algorithms, running time complexity is least dependent on the initial ordering of the input that is O(n × log₂n)

Insertion sort:

In Insertion sort, the worst-case takes Θ (n2) time, the worst case of insertion sort is when elements are sorted in reverse order. In that case the number of comparisons will be like:

\(\mathop \sum \limits_{{\rm{p}} = 1}^{{\rm{N}} - 1} {\rm{p}} = 1 + 2 + 3 + \ldots . + {\rm{N}} - 1 = {\rm{\;}}\frac{{{\rm{N}}\left( {{\rm{N}} - 1} \right)}}{2} - 1\)

This will give Θ (n2) time complexity.

Quicksort:

In Quicksort, the worst-case takes Θ (n2) time. The worst case of quicksort is when the first or the last element is chosen as the pivot element.

\(\mathop \sum \limits_{{\rm{p}} = 1}^{{\rm{N}} - 1} {\rm{p}} = 1 + 2 + 3 + \ldots . + {\rm{N}} - 1 = {\rm{\;}}\frac{{{\rm{N}}\left( {{\rm{N}} - 1} \right)}}{2} - 1\)

This will give Θ (n2) time complexity.

Recurrence relation for quick sort algorithm will be,

T (n) = T (n-1) + Θ (n)

This will give the worst-case time complexity as Θ (n2).

It is clear that quick sort and insertion sort time complexity depend on the input sequence

Important Point

Concept

The stability of a sorting algorithm is concerned with how the algorithm treats equal (or repeated) elements.

A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted.

Some sorting algorithms are stable by nature like Insertion sort, Merge Sort, Bubble Sort, etc. And some sorting algorithms are not, like Heap Sort, Quick Sort, etc.

Insertion sort:

In Insertion sort, the worst-case takes Θ (n²) time, the worst case of insertion sort is when elements are sorted in reverse order. In that case the number of comparisons will be like:

\(\mathop \sum \limits_{{\rm{p}} = 1}^{{\rm{N}} - 1} {\rm{p}} = 1 + 2 + 3 + \ldots . + {\rm{N}} - 1 = {\rm{\;}}\frac{{{\rm{N}}\left( {{\rm{N}} - 1} \right)}}{2} - 1\)

This will give Θ (n²) time complexity.

Merge sort:

In Merge sort, the worst-case takes Θ (n log n) time. Merge sort is based on the divide and conquer approach. Recurrence relation for merge sort will become:

T(n) = 2T (n/2) + Θ (n)

T(n) = n + Θ (n)

T (n) = n × logn

Quicksort:

In Quicksort, the worst-case takes Θ (n²) time. The worst case of quicksort is when the first or the last element is chosen as the pivot element.

Diagram

\(\mathop \sum \limits_{{\rm{p}} = 1}^{{\rm{N}} - 1} {\rm{p}} = 1 + 2 + 3 + \ldots . + {\rm{N}} - 1 = {\rm{\;}}\frac{{{\rm{N}}\left( {{\rm{N}} - 1} \right)}}{2} - 1\)

This will give Θ (n²) time complexity.

Recurrence relation for quick sort algorithm will be,

T (n) = T (n-1) + Θ (n)

This will give the worst-case time complexity as Θ (n²).

Merge sort:

Merge sort is based on the divide and conquer approach.

Recurrence relation for merge sort will become:

T(n) = 2T (n/2) + Θ (n)

Using Master’s theorem

T (n) = n × log₂n

Therefore, the time complexity of Merge Sort is θ(nlogn).