COMPUTER SCIENCE AND ENGINEERING
ALGORITHMS
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
When a list is kept as one and compared
|
|
|
List is split into 2 and merged together
|
|
|
List is split into 2 and kept seperate
|
|
|
Nothing
|
Detailed explanation-1: -If the list has more than one item, we split the list and recursively invoke a merge sort on both halves. Once the two halves are sorted, the fundamental operation, called a merge, is performed. Merging is the process of taking two smaller sorted lists and combining them together into a single, sorted, new list.
Detailed explanation-2: -The merge only works with sorted lists. Thus you divide until you get one or two elements, which can be trivially sorted either by leaving it alone or with a swap. Then you do the merging which takes elements in sequence from one or the other list.
Detailed explanation-3: -Merge sort keeps on dividing the list into equal halves until it can no more be divided. By definition, if it is only one element in the list, it is sorted. Then, merge sort combines the smaller sorted lists keeping the new list sorted too.
Detailed explanation-4: -Merge Sort is a divide and conquer algorithm. It consists of two parts: 1) splitting the original list into smaller sorted lists recursively until there is only 1 element in the list, 2) merging back the presorted 1-element lists into 2-element lists, 4-element lists, and so on recursively.
Detailed explanation-5: -In theory, it’s because the merge procedure needs to take two sorted lists. A 4-elements list isn’t sorted, while a one-element list is. In practice, we don’t split lists to one-element. Because merge sort isn’t the most efficient sorting algorithm for small lists, insertion sort is.