c++ - Insertion Sort algorithm by using binary search error

Question

I run the following code which is Insertion Sort algorithm that use binary search to find the right position of the item being inserted instead of linear search but there are two numbers in the results not sorted correctly!

#include <iostream>
using namespace std;

void insertion_sort (int a[], int n /* the size of array */)
{
    int i, temp,j;
    for (i = 1; i < n; i++)
    {
        /* Assume items before a[i] are sorted. */
        /* Pick an number */
        temp = a[i];

        /* Do binary search to find out the
           point where b is to be inserted. */

        int low = 0, high = i - 1, k;

        while (high-low>1)
        {
            int mid = (high + low) / 2;

            if (temp <= a[mid]) 
                high = mid;
            else 
                low = mid;
        }

        /* Shift items between high and i by 1 */
        for (k = i; k > high; k--)
            a[k] = a[k - 1];

        a[high] = temp;
    }
}


int main()
{
    int A[15]={9,5,98,2,5,4,66,12,8,54,0,11,99,55,13};
    insertion_sort(A,15);
    for (int i=0; i<15; i++)
        cout<<A[i]<<endl;
    system("pause");
    return 0;
}

Output:

Why?

Answer 1

A few things to be noticed here:

1. Binary search does not give you anything, as you need to shift all elements to make space anyway. So it actually increases the overall cost of your algorithm (though not asymptotically).

2. As this is C++ there is no need to declare k anywhere before the for loop in which it is used (just use for(int k; ...)).

3. Analyse your algorithm's beginning: i=0 -> low = high = 0. So your while loop does not execute. Then, no matter if the element should be moved or not, your for (k) loop swaps elements 0 and 1. This is error number 1.

4. Second iteration of i: the while loop does not execute once again, as low = 0 and high = 1, and once again no matter what you swap at least elements 1 and 2. Error number 2.

5. Now notice that every next iteration will, no matter what, move the element which was initially at index 0 (in your test code it is =9) further and further, to the last index.

So you may see just after checking firts two iterations of for(i) loop that the assumption that elements before a[i] are sorted is wrong, and therefore the algorithm is wrong as well.

Answer 2

#include <iostream>
using namespace std;

void insertion_sort (int a[], int n /* the size of array */)
{
    int i, temp,j;
    for (i = 1; i < n; i++)
    {
        /* Assume items before a[i] are sorted. */
        /* Pick an number */
        temp = a[i];

        /* Do binary search to find out the
           point where b is to be inserted. */

The high bound should be above the range and exclusive of the search, because you may need to insert at the end, i.e. do nothing.

        // int low = 0, high = i - 1, k;
        int low = 0, high = i, k;

Here the condition should be low < high, not low + 1 < high

        // while (high-low>1)
        while (low < high)
        {
            int mid = (high + low) / 2;

            if (temp <= a[mid]) 
                high = mid;
            else 

Once you have a[mid] strictly greater than temp, the lowest possible position to insert is mid + 1.

                // low = mid;
                low = mid + 1
        }

        /* Shift items between high and i by 1 */
        for (k = i; k > high; k--)
            a[k] = a[k - 1];

        a[high] = temp;
    }
}


int main()
{
    int A[15]={9,5,98,2,5,4,66,12,8,54,0,11,99,55,13};
    insertion_sort(A,15);
    for (int i=0; i<15; i++)
        cout<<A[i]<<endl;
    system("pause");
    return 0;
}

Answer 3

Easiest possible fix: initialize low and high as int low = -1, high = i;. What you wanted to do was to find indices low and high such that all elements from 0 to low are < a[i] and all elements from high to i-1 are ≥ a[i]. Your initialization didn't work since it didn't capture the corner cases when all elements a[0], ..., a[i-1] are greater than a[i] and the corner case when all these elements were less than a[i].