What are issues of binary sort?

Answer 1

There's no such thing as a binary sort. You are possibly referring to a binary insertion sort which is based upon binary search.

The most efficient binary search makes use of a sorted array. This offers us constant-time random-access to any element. By keeping track of the upper and lower indices of a subset, we can easily calculate the middle element of that subset:

middle = (upper - lower) / 2 + lower

Given an array A of length n, we can search for a given value as follows:

unsigned search (const int* A, const unsigned n, int value) { int lower = 0;

int upper = n;

while (lower<upper) {

int middle = (upper - lower) / 2 + lower;

if (value == A[middle])

return middle;

else if (value < A[middle])

upper = middle;

else

lower = middle+1;

}

return n;

}

Note that we return the index of the value if found. If not, we return n, which is the index one-past-the-end of the array. We can use the algorithm as follows:

unsigned find;

const unsigned max = 10;

int X[max] = {3, 5, 7, 9, 11, 13, 15, 17, 19, 21}; // sorted array

find = search (X, max, 15); // search for value 15

assert (find==6);

find = search (X, max, 20); // search for non-existent value

assert (find==max);

We can modify the binary search algorithm such that we can locate the insertion point for a new value, thus creating a binary insertion sort. First, we locate the insertion point:

unsigned find_insert (const int* A, const unsigned n, int value) {

int lower = 0;

int upper = n;

while (lower<upper) {

int middle = (upper - lower) / 2 + lower;

if (A[middle]>value && (middle==0 A[middle-1]<=value))

return middle;

else if (value < A[middle])

upper = middle;

else

lower = middle+1;

}

return n;

}

Note that we're now looking for a value that is greater than our value such that the previous value is less than or equal to our value or there is no previous value.

With this algorithm in place, we can now perform the insertion:

unsigned insert (int* A, const unsigned n, int value) {

unsigned index = find_insert (A, n, value);

for (unsigned i=n; i>index; --i) A[i] = A[i-1];

A[index] = value;

return index;

}

Note that, prior to invoking the insertion, you must reserve one or more unused elements at the end of the array (at index n or beyond).