Why does the sorting algorithm work correctly?

Question

I got a sorting algorithm. I know it could have been written in many other and more simple ways but that's not the point of my question.

Here is the algorithm:

sort(A : Array of N, i : N, j : N)
assert j-i+1 isTwoPotency
if A[i] > A[j] then swap A[i] and A[j]
if i+1 < j then
    k:= (j − i + 1)/4
    sort(A, i, j − 2k)
    sort(A, j − 2k + 1, j)
    sort(A, i + k, j − k)
    sort(A, i, j − 2k)
    sort(A, j − 2k + 1, j)
    sort(A, i + k, j − k)

My question is, why does the algorithm work correctly in the following case?

sort(A, 1, length(A))

and the array would be:

A[1 . . . length(A)]

length(A) is a two potency and we can assume that there are no identical numbers inside the array. I already tested it, got no errors so I assume it works correctly. But how can I prove that the algorithm always works correctly in these conditions?

And I am wondering how long does the algorithm needs as running time. It would be great if you could give me the running time as big theta notation (that's the one I understand the best)

f(n) = Θ(g(n))

If you don't know, if your code works correctly, then write tests, which will check that. — michaJlS
– michaJlS, Commented May 25, 2016 at 7:34
I already tested it, I just want the prove as mentioned an the running time. (I edited the question) — Elfie
– Elfie, Commented May 25, 2016 at 7:39
I tested out the code with 16 numbers, its sorted all the number from index 2 forward, but the first number was unsorted.. so it almost worked, but not really, at least not with the numbers I tested. my test numbers:(11,21,13,41,15,16,71,28,19,10,1,12,3,14,5,6). your algorithm sorted it to:(11,1,3,4,6,10,12,13,14,15,16,19,21,28,41,71).. notice the first number did not get sorted. — Sergio Fernandez
– Sergio Fernandez, Commented May 25, 2016 at 7:40
no there is a difference in your code and mine, your array starts from 0. not 1, when I modified by array to start from 0, and changed the line, swap(a[i],a[j]) to sawp(a[i-1],a[j-1]) it works, so, I'll loop though teh code to see why it makes a difference, but thats what you did different from teh pesudo code. your array stared from 0. — Sergio Fernandez
– Sergio Fernandez, Commented May 25, 2016 at 8:04

augurar · Accepted Answer · 2016-05-25 09:24:51Z

Correctness

Divide the array into four quarters, A1 through A4, and consider the sub-array each element should end up in.

After the first two recursive calls, all elements that belong in A1 are located in A1 or A3. Similarly all A4 elements are located in A2 or A4.
After the third recursive call, all A1 elements are in A1 or A2, and all A4 elements are in A3 or A4.
After the next two recursive calls, all A1 elements are in A1 in sorted order, and all A4 elements are in A4 in sorted order. This leaves all A2 and A3 elements in either A2 or A3.
After the last recursive call all A2 and A3 elements are in the correct sub-array in sorted order. Thus the array is sorted.

Illustration:

Runtime

Notice that when we execute the algorithm on an array of length n, we have to execute the algorithm six times on arrays of length n/2. This yields the following recurrence:

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

Solving the recurrence we get T(n) = O(6^log2(n)) = O(n^log2(6)) ≈ O(n^2.585)

Collectives™ on Stack Overflow

Why does the sorting algorithm work correctly?

1 Answer 1

Correctness

Runtime

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Correctness

Runtime

Comments

Your Answer

Sign up or log in

Post as a guest

Related