Computer Science

Sorting Algorithms

Sorting Algorithms: Level 3 challenges

     

Consider the modification of a 4 way merge sort which instead of dividing an array into two subarrays, 4-way merge sort divides the array into four sub-arrays and sorts each individual array recursively.

In the 2-way merge sort we have an index for each of the two sorted sub-arrays and we compare the elements they are pointing to and in worst case we perform 2k12k-1 comparison where kk is the length of each array. Similarly in a 44-way merge sort each of size kk we have and index for each of the four arrays. It takes 33 comparisons to determine the smallest of the four. In worst case we must do this until each list has one element left for a total of 12(k1)12(k-1) comparison. Finally we perform 3+2+13+2+1 comparisons to finish the remaining list, thus for a total of 12k612k-6 comparisons.

Based on the above merge procedure which of the following represents the correct running time for a 44 way merge sort?

Details and Assumptions

-Ignore constant terms.

Is it possible to come up with a better worst case running time? is it asymptotically better?

Suppose you are give kk sorted arrays each of nn elements. Using the standard merge subroutine you merge the first 2 arrays and merge the 3rd array to the already merged arrays, and so on until you merge the kk-th array, what is the running time of this procedure?

We know that the insertion sort algorithm has a worth-case running time of O(n2)O(n^{2}) in general case. What if we could bound the algorithm for specific instance of the problem. One way to do that is by checking the number of swap operations needed by insertion algorithm to sort a list.

In the permutation of a1ana_{1}\cdots a_{n} of nn distinct elements the list inversion are pair of elements (ai,aj)(a_{i},a_{j}) such that i<ji<j and ai>aja_{i} > a_{j}. What is the worst-case running time if the inputs are restricted to permutations of 1n1\cdots n with at most nn inversions?

×

Problem Loading...

Note Loading...

Set Loading...