Algorithm: Sort sequence of 0/1 using only comparisons

Question

I'm trying to improve my algorithms knowledge and am trying to solve the following problem from Skiena's Algorithm Design Manual:

4-26 Consider the problem of sorting a sequence of n 0’s and 1’s using comparisons. For each comparison of two values x and y, the algorithm learns which of x y holds.

(a) Give an algorithm to sort in n − 1 comparisons in the worst case. Show that your algorithm is optimal.

(b) Give an algorithm to sort in 2n/3 comparisons in the average case (assuming each of the n inputs is 0 or 1 with equal probability). Show that your algorithm is optimal.

This is my solution for (a):

void sort(int arr[], int length) {
    int last_zero = -1;
    for (int i = 1; i < length; i++) {
        if (arr[i] < arr[i-1]) {
            int tmp = arr[i];
            arr[i] = arr[++last_zero];
            arr[last_zero] = tmp;
        } else if (arr[i] > arr[i-1]) {
            last_zero = i-1;
        }
    }
    return;
}

Is there a better way to do this?

I'm not sure how to approach part (b). There's a similar question here but I don't understand the explanation there.

Edit: Apparently this has been deemed too vague so let me follow-up based on the responses.

I am following up to @amit's response. I don't quite understand this part:

(such that i_k != i_h for k!= h, i_k != i_h for k!= h, and i_k != j_h for all k,h).

Regardless, I think I generally understand the idea you propose for solving part (b). As I tried to write code for it, however, I'm finding it difficult to complete. This is what I have so far and based on my testing it successfully sorts all (0,1) and (1,0) pairs and pushes the equal pairs to the end of the array so I end up with {all zeros, all ones, equal pairs}. I'm trying to actually shift array elements around as opposed to counting the numbers of 0s and 1s. I'm stuck on how to proceed from what I have so far:

int compare(int a, int b);
void shift_right(int arr[], int start, int end);
int prob_4_26_b(int arr[], int length) {
    int last_zero = -1;
    int last_one = -1;
    for (int i = 0; i < length; i += 2) {
        int tmp = compare(arr[i], arr[i+1]);
        int cur_zero, cur_one;
        if (tmp == 0) {
            continue;
        }

        cur_zero = i;
        cur_one = i + 1;
        /* We have a 0 and a 1 */
        /* If this is the first zero we have put it at index 0
         and shift everything from index 0 to cur_zero-1 right by 1.
         last_zero = 0 and if there are ones last_one++ */
        if (last_zero == -1) {
            int start = 0;
            int end = cur_zero - 1;
            shift_right(arr, start, end);
            arr[0]=0;
            last_zero = 0;
            if (last_one != -1) {
                last_one++;
            }
        }
        /* If this is not the first zero we have then put it at
         last_zero+1 and shift everything from last_zero+1 to cur_zero-1
         right by 1. last_zero++ and if we have ones last_one++. */
        else {
            int start = last_zero + 1;
            int end = cur_zero - 1;
            shift_right(arr, start, end);
            arr[last_zero+1] = 0;
            last_zero++;
            if (last_one != -1) {
                last_one++;
            }
        }

        /* If this is the first one we have put it after the last_zero.
         Shift everything from last_zero+1 to cur_one-1 right by 1.
         last_one = last_zero+1. */
        if (last_one == -1) {
            int start = last_zero + 1;
            int end = cur_one-1;
            shift_right(arr, start, end);
            arr[last_zero+1] = 1;
            last_one = last_zero + 1;
        }
        /* If this is not the first one we have put it at last_one+1
         and shift everything from last_one+1 to cur_one-1 right by 1.
         last_one++ */
        else {
            int start = last_one + 1;
            int end = cur_one - 1;
            shift_right(arr, start, end);
            arr[last_one+1] = 1;
            last_one++;
        }
    }
    return 0;
}

void shift_right(int arr[], int start, int end) {
    for (int i = end; i >=start; i--) {
        arr[i+1] = arr[i];
    }
}

int compare(int a, int b) {
    if (a < b)
        return -1;
    else if (a > b)
        return 1;
    else
        return 0;
}

Answer 1

In order to do the second part, you need to first realize checking comp(a[i], a[i+1]), and comp(a[i+1], a[i+2]) are not unrelated. The answer of the first might help you get the answer to the second.

To utilize it, first split the sequence to pairs,(a[i1],a[j1]), (a[i2],a[j2]),..., (a[i_n/2], a[j_n/2]). (such that i_k != i_h for k!= h, i_k != i_h for k!= h, and i_k != j_h for all k,h).

Compare each such pair. On average (assuming the bits are uniformly distributed), you will have n/4 conclusive answers of a[i] < a[j] or the other way around, and for the remaining n/4, you will have equalities.

So, first you can easily sort those with conclusive answer (the smaller at the beginning, the bigger at the end).

Next, you will recursively invoke the algorithm on the reminder. But here comes the "trick", if you know that for some i,j: a[i] = a[j], you don't need to get answer for both. Answer for one of them will tell you the value of the second as well.
This means you can recursively invoke with only n/4 elements, and not n/2 (on average).

The stop clause will be when you have a single element, and just compare it to 0 to know its value.

This gives you complexity function of:

T(1) = 1
T(n) = n/2 + T(n/4)

After some mathematics to find a close form for this recursive formula (or consulting with wolfram alpha), you will find that T(n) = (2n+1)/3