Optimizing a sorting algorithm by replacing the one of the recursion with a another function

Question

Currently I have this sorting algorithm:

public static void sort(int[] A, int i, int j) {
    if (i == j) return;
    if(j == i+1) {
        if(A[i] > A[j]) {
            int temp = A[i];
            A[i] = A[j];
            A[j] = temp;
        }
    } 
    else {
        int k = (int) Math.floor((j-i+1)/3);
        sort(A,i, j-k);
        sort(A,i+k, j);
        sort(A,i,j-k);
    }
}

It's sorting correctly, however, the asymptotic comparison is quite high: with T(n) = 3T(n-f(floor(n/3)) and f(n) = theta(n^(log(3/2)3)

Therefore, I'm currently thinking of replacing the third recursion sort(A,i,j-k) with an newly written, iterative method to optimize the algorithm. However, I'm not really sure how to approach the problem and would love to gather some ideas. Thank you!

Answer 1

If I understand this correct, you first sort the first 2/3 of the list, then the last 2/3, then sort the first 2/3 again. This actually works, since any misplaced items (items in the first or last 2/3 that actually belong into the last or first 1/3) will be shifted and then correctly sorted in the next pass of the algorithm.

There are certainly two points that can be optimized:

• in the last step, the first 1/3 and the second 1/3 (and thus the first and second half of the region to sort) are already in sorted order, so instead of doing a full sort, you could just use a merge-algorithm, which should run in O(n)
• instead of sorting the first and last 2/3, and then merging the elements from the overlap into the first 1/3, as explained above, you could sort the first 1/2 and last 1/2 and then merge those parts, without overlap; the total length of array processed is the same (2/3 + 2/3 + 2/3 vs. 1/2 + 1/2 + 2/2), but the merging-part will be faster than the sorting-part

However, after the second "optimization" you will in fact have more or less re-invented Merge Sort.