1. Introduction

A binary array consists of only the integers 0 and 1. Sorting such an array means that all zeros should be moved to the left (or start) of the array, and all ones to the right (or end). The challenge is to accomplish this in linear time, O(n), without using any sorting function.

2. Program Steps

1. Initialize two pointers, left and right.

2. Move the left pointer to the right while the left element is 0.

3. Move the right pointer to the left while the right element is 1.

4. If left is less than right, swap the elements at the left and right pointers.

5. Continue until left is no longer less than right.

3. Code Program

public class BinaryArraySorting {

    public static void sortBinaryArray(int[] A) {
        int left = 0, right = A.length - 1;

        while (left < right) {
            while (A[left] == 0 && left < right) {
                left++;
            }

            while (A[right] == 1 && left < right) {
                right--;
            }

            if (left < right) {
                A[left] = 0;
                A[right] = 1;
                left++;
                right--;
            }
        }
    }

    public static void main(String[] args) {
        int[] A = {1, 0, 1, 0, 1, 0, 0, 1};

        sortBinaryArray(A);

        for (int i = 0; i < A.length; i++) {
            System.out.print(A[i] + " ");
        }
    }
}

Output:

0 0 0 0 1 1 1 1

4. Step By Step Explanation

1. We use the two-pointer technique. One pointer, left, is initialized at the start and the other pointer, right, at the end.

2. If the element at left is 0, then it's already at the correct position, and we move the left pointer to the right.

3. Similarly, if the element at right is 1, then it's already in its correct position, and we move the right pointer to the left.

4. If the element at left is 1 and the element at right is 0, their positions are swapped.

5. We continue this process until the left pointer is no longer less than the right pointer.

This approach ensures that the binary array gets sorted in linear time, which is more efficient than using any built-in sort functions for this specific case.