折半插入排序

#include<iostream>
#include<malloc.h>//但是其时间复杂度还是O(n^2) 
using namespace std;
void BInsertSort(int* &Arr,int len);
 int main(void)
 {
    int len;
    cout<<"请输入长度：";
    cin>>len;cout<<endl;
    int *pArr=(int *)malloc(sizeof(int)*len);
    cout<<"请输入数值：";
    for(int i=0;i<len;i++)
    {
        cin>>pArr[i];
     }
     cout<<"排序前：";
    for(int i=0;i<len;i++)
    {
        cout<<pArr[i]<<" ";
     }
     cout<<endl;cout<<"排序后：";
     BInsertSort(pArr,len);
     for(int i=0;i<len;i++)
    {
        cout<<pArr[i]<<" ";
     }
     cout<<endl; 
    return 0;
 }
 void BInsertSort(int* &s,int len)
 {
    for(int i=1;i<len;i++)
    {
        int t=s[i];
        int low=0,high=i-1,mid;
        while(low<=high)
        {
            mid=(low+high)/2;
            if(s[i]<=s[mid]) 
            {
                high=mid-1;
            }
            else
            {
                low=mid+1;
            }
        }   
        //最后，low或者high+1为放入的位置。 
        for(int j=i-1;j>=low;j--)//向后移动 
        {
            s[j+1]=s[j];
         }
         s[low]=t;
    }   

    
    
 }