Explain why SomeSort correctly sorts its input array A assum

Explain why SomeSort correctly sorts its input array A, assuming that n = e b + 1 is the length of the array (your argument need not be a formal proof but should be detailed enough to be convincing).

Find a recurrence for the worst-case running time of SomeSort. Give a tight (i.e. ) asymptotic bound for the worse-case running time of SomeSort (Hint: for simplicity assume that n = 3k for some constant k).

By comparing SomeSort with insertion sort, merge sort, heap-sort, and quicksort argue if this simple algorithm is effcient.

Solution

Let us assume the n=3k. Now we are dividing the array in to three parts. Each of size k, let us call them part1,part2 and part3.

In the line

We are sorting sub-array with elements of part1 and part2. After this is executed this sub array is sorted. So after this is sorted all the numbers in part2 will be greater than all the numbers in part1.

Here we are sorting sub-array with elements of part2 and part3. After this is executed this sub array is sorted. So after this is sorted all the numbers in part3 will be greater than all the numbers in part2. Because of the previous we already know that all the elements in part 2 are greater than part1. Now the elements in part3 will be greater than or equal to the elements in part2 previously. So we can also state that part 3 > part2 and part3 > part1. So the greatest k elements in the whole array are now in part3.

Now

Again we are sorting part1 and part2 combined. After this is done the first 2k elements will have been sorted and these elements are less than k elements in part3, which are also sorted. So the whole array is now sorted.

The time equation will be:

T(n) = 3T(2n/3)+O(1).

In master theorms format a =3 b=1.5 c=1

log(b)a > c so T(n) = O(n^ ( log(1.5)3 ) )