Question

2. Here is a sorting algorithm that I like to use. Given an unsorted list of size n, let Xx represent the data in location k of the unsorted list. Compare xi to X2 and switch if necessary so that they are in sorted order, smallest first. Compare Xn-1 and Xn and switch if necessary so that they are in sorted order, smallest first. • Compare x3 with its left neighbors, switching if necessary so that the 3 first entries are sorted. • Compare Xn-2 with its right neighbors, switching if necessary so that the last 3 entries are sorted. • Continue in this manner with X4, Xn-3, X5, Xn-4...until you have sorted element X1/2. I now have two sorted lists, each of size n/2. • Merge the two sorted lists to create one sorted list of size n. Compare the data in location 1 with the data in location n/2 selecting the smallest. Compare the larger of those two elements with the next element in the opposing list and select the smallest and so on. a) State the running time of this algorithm using the most accurate informative) order notation possible. b) Prove the worst-case I running time of this algorithm. Full credit is given for the most clear and concise proofs.

Answer 1

First thing this algorithm is not a recursive algorithm rather it's an iterative one. Now, to calculate its time complexity we need to calculate the number of comparisons.

Note: In all the cases below I will decompose the time complexity in two terms-> 1.) Sorting the two parts of the given array and 2.) Merging them. The merging operation is Θ(n) regardless of any case.

a.) Best Case:

In the best case, all elements will be already sorted so the number of comparisons will n/2 in the first part and n/2 in the second part i.e. n. Hence the time complexity is Θ(n).

Reason: In the best case, each element will be compared only once because it is already sorted.

Total = Θ(n) + Θ(n) = Θ(n)    (comparisons + merge).

b.) Worst Case:

In the worst case, all elements will be sorted in reverse order so the number of comparisons will be 2x( 1 + 2 + 3 + ... + n/2 -1) = n(n - 2)/4 i.e. time complexity is Θ​​​​​​​(n²).

Reason: In the worst case, each element will be compared with all the elements on the left side for the left part of the array and the same goes for the right part.

Total = Θ(n) + Θ(n²) = Θ(n²)    (comparisons + merge).

This algorithm is similar to insertion sort so the average case complexity will be same i.e. O(n²).