1. Which of the following sorting algorithm makes use of merge sort?
a) tim sort
b) intro sort
c) bogo sort
d) quick sort
Explanation: Tim sort is a hybrid sorting algorithm as it uses more than one sorting algorithm internally. It makes use of merge sort and insertion sort.
2. Which of the following sorting algorithm does not use recursion?
a) quick sort
b) merge sort
c) heap sort
d) bottom up merge sort
Explanation: Bottom up merge sort uses the iterative method in order to implement sorting. It begins by merging a pair of adjacent array of size 1 each and then merge arrays of size 2 each in the next step and so on.
3. Merge sort uses which of the following algorithm to implement sorting?
a) backtracking
b) greedy algorithm
c) divide and conquer
d) dynamic programming
Explanation: Merge sort uses the technique of divide and conquer in order to sort a given array. It divides the array into two halves and applies merge sort algorithm to each half individually after which the sorted versions of these halves are merged together.
4. What is the average case time complexity of standard merge sort?
a) O(n log n)
b) O(n2)
c) O(n2 log n)
d) O(n log n2)
Explanation: The recurrence relation for merge sort is given by T(n) = 2T(n/2) + n. This can be solved using master’s theorem and is found equal to O(n log n).
5. What is the auxiliary space complexity of standard merge sort?
a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)
Explanation: The merging of two sorted arrays requires an additional space of n due to which the auxiliary space requirement of merge sort is O(n). Thus merge sort is not an in place sorting algorithm.
6. What is the auxiliary space complexity of bottom up merge sort?
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)
Explanation: The auxiliary space complexity of bottom up merge sort is same as standard merge sort as both uses the same algorithm for merging the sorted arrays which takes o(n) space. But bottom up merge sort does not need to maintain a call stack.
7. What is the average time complexity of bottom up merge sort?
a) O(n log n)
b) O(n2)
c) O(n2 log n)
d) O(n log n2)
Explanation: The merge function in the bottom up merge sort takes O(n) time which is placed inside the for loop. The loop runs for O(log n) time, thus the overall time complexity of the code becomes O(n log n).
8. Merge sort uses which of the following method to implement sorting?
a) merging
b) partitioning
c) selection
d) exchanging
Explanation: Merge sort implements sorting by merging the sorted versions of smaller parts of the array. Thus its method of sorting is called merging.
9. Bottom up merge sort uses recursion.
a) true
b) false
Explanation: Bottom up merge sort uses the iterative method in order to implement sorting. It begins by merging a pair of adjacent array of size 1 each and then merge arrays of size 2 each in the next step and so on.
10. Bottom up merge sort is a stable sort.
a) true
b) false
Explanation: Bottom up merge sort like standard merge sort is a stable sort. This implies that the relative position of equal valued elements in the input and sorted array remain same.
Design and Analysis of Algorithms
The Ballet of Sorting: Merge Sort's Grand Entrance
Picture a ballet where dancers gracefully twirl, seamlessly merging and splitting, creating a harmonious dance. That's Merge Sort for you! In the algorithmic ballet, Merge Sort takes the stage with elegance, boasting an impressive divide-and-conquer routine.
Divide and Conquer: The Secret Sauce
Merge Sort's mantra is simple: divide, conquer, and then party with sorted arrays. It breaks down the chaos into manageable bits, sorts them individually, and then orchestrates a grand reunion. It's like the maestro of sorting algorithms conducting a symphony of order.
Behind the Scenes: A Peek into Merge Sort's Dressing Room
Merge Sort's dressing room is like a zen garden for arrays. It doesn't mess up the order, and it takes its time – no rush here! The algorithm compares elements patiently, ensuring each pair finds its rightful place. It's like matchmaking for numbers, but without the awkward conversations.
As we bid adieu to our algorithmic journey, remember that Merge Sort isn't just an algorithm; it's a sorting symphony. So, next time you face a chaotic array, let Merge Sort lead the dance of order in the grand ballroom of algorithms. Cheers to sorting and algorithmic elegance!