1. Merge sort can be implemented using O(1) auxiliary space.
a) true
b) false
Explanation: Standard merge sort requires O(n) space to merge two sorted arrays. We can optimize this merging process so that it takes only constant space. This version is known as in place merge sort.
2. What is the worst case time complexity of merge sort?
a) O(n log n)
b) O(n2)
c) O(n2 log n)
d) O(n log n2)
Explanation: The time complexity of merge sort is not affected by worst case as its algorithm has to implement the same number of steps in any case. So its time complexity remains to be O(n log n).
3. Which of the following method is used for sorting in merge sort?
a) merging
b) partitioning
c) selection
d) exchanging
Explanation: Merge sort algorithm divides the array into two halves and applies merge sort algorithm to each half individually after which the two sorted halves are merged together. Thus its method of sorting is called merging.
4. What will be the best case time complexity of merge sort?
a) O(n log n)
b) O(n2)
c) O(n2 log n)
d) O(n log n2)
Explanation: The time complexity of merge sort is not affected in any case as its algorithm has to implement the same number of steps. So its time complexity remains to be O(n log n) even in the best case.
5. Which of the following is not a variant of merge sort?
a) in-place merge sort
b) bottom up merge sort
c) top down merge sort
d) linear merge sort
Explanation: In-place, top down and bottom up merge sort are different variants of merge sort. Whereas linear merge sort is not a possible variant as it is a comparison based sort and the minimum time complexity of any comparison based sort is O(n log n).
6. Choose the incorrect statement about merge sort from the following?
a) it is a comparison based sort
b) it is an adaptive algorithm
c) it is not an in place algorithm
d) it is stable algorithm
Explanation: Merge sort is not an adaptive sorting algorithm. This is because it takes O(n log n) time complexity irrespective of any case.
7. Which of the following is not in place sorting algorithm by default?
a) merge sort
b) quick sort
c) heap sort
d) insertion sort
Explanation: Quick sort, heap sort, and insertion sort are in-place sorting algorithms, whereas an additional space of O(n) is required in order to merge two sorted arrays. Even though we have a variation of merge sort (to do in-place sorting), it is not the default option. So, among the given choices, merge sort is the most appropriate answer.
8. Which of the following is not a stable sorting algorithm?
a) Quick sort
b) Cocktail sort
c) Bubble sort
d) Merge sort
Explanation: Out of the given options quick sort is the only algorithm which is not stable. Merge sort is a stable sorting algorithm.
9. Which of the following stable sorting algorithm takes the least time when applied to an almost sorted array?
a) Quick sort
b) Insertion sort
c) Selection sort
d) Merge sort
Explanation: Insertion sort takes linear time to sort a partially sorted array. Though merge and quick sort takes O(n*logn) complexity to sort, merge sort is stable. Hence, Merge sort takes less time to sort partially sorted array.
10. Merge sort is preferred for arrays over linked lists.
a) true
b) false
Explanation: Merge sort is preferred for linked list over arrays. It is because in a linked list the insert operation takes only O(1) time and space which implies that we can implement merge operation in constant time.
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!