折り返し挿入ソートコード実装

package sort;

/**
 * @author linjia
 *  
 */
public class BinaryInsertSort {

	public int[] binSort(int r[], int n) {
		
		for(int i=1;i<n;i++)
		{
			int temp=r[i];
			int low=0;
			int high=i-1;
			
			while(low<=high)
			{
				int mid=(low+high)/2;               // 
				if(temp<r[mid])high=mid-1;      // 
				else low=mid+1;                      // 
			}
			
			System.out.println("low:"+low+" high:"+high);
			
			for(int j=i-1;j>=high+1;j--)
			{
				r[j+1]=r[j];
			}
			
			r[high+1]=temp;
		}
		
		return r;
	}

	public static void main(String[] args) {
		int[] test = { 3, 9, 8, 55, 97, 33, 6, 1 };

		test = new BinaryInsertSort().binSort(test, test.length);

		for (int i : test) {
			System.out.print(i+" ");
		}
	}
}

結果:

low:1 high:0
low:1 high:0
low:3 high:2
low:4 high:3
low:3 high:2
low:1 high:0
low:0 high:-1
1 3 6 8 9 33 55 97 

 
直接挿入ソートと比較して,折半挿入ソートはキーワードの「比較」回数を著しく減少させたが,記録「移動」回数は変わらないため,時間複雑度はn(o^2)であった.