binary insertion sort algorithm

Question

i have tried to implement binary insertion sort algorithm from here

http://www.brpreiss.com/books/opus5/html/page487.html

here is code

public class binary_insertion {
public static void sort(int a[],int n){
     for (int i=0;i<n;++i ){
           int temp=a[i];
         int left=0;
         int right=i;
          while (left<right){
              int middle=(left+right)/2;
              if (temp>=a[middle])
                  left=right+1;
              else
                   right=middle;
          }
           for (int j=i;j>left;--j){
                swap(a,j-1,j);
           }
     }



}

    public static void main(String[] args) {
     int a[]=new int[]{12,10,34,23,9,7,8,5,6};
     sort(a,a.length);
      for (int i=0;i<a.length;i++){
           System.out.println(a[i]);
      }
    }
    public static void swap(int a[], int i,int j){
      int k=a[i];
       a[i]=a[j];
        a[j]=k;
    }

}

and result is

5
7
6
9
8
10
12
34
23

please help

Answer 1

First thing that stands out is here:

      while (left<right){
          int middle=(left+right)/2;
          if (temp>=a[middle])
              left=right+1;
          else
               right=middle;

You want left = middle + 1.

The code works for me with that change.