I have been given two True/False questions regarding sorting an array. The questions are as following -
Question A
Given an array A with 3n keys that contains three equal parts A[1,n], A[n+1,2n] and A[2n+1,3n], each with n keys. Each part is sorted. Is possible to sort the keys of A into a new array B in O(n) steps (worst case)?
Question B
Given an array A with 10n keys that are comparable using a binary function that returns which element is bigger or if the elements are equal. The array is split into n equal parts, each with 10 keys. Each part is sorted. Is it possible to sort the keys of A into a new array B in O(n) steps (worst case)?
The solution to question A is that we can use merge() fucntion from MergeSort to sort the array.
The solution to question B is that it is not possible, as it violates the Ω(nlog(n)) lower bound for comparison based sorting algorithms
And I fail to see the difference between the two questions.. Is it because in question B we first need to apply the function? Why does it prohibits us from using merge() aswell? I don't see the logic behind the assumption that the two scenarios are different and I feel that I'm missing something important.