插入排序的子过程会向一个有序数组中插入一个元素，请 利用训练9中写的bsearch方法，对这个过程进行优化：

    直接利用bsearch找到需要插入元素的位置，然后执行插入

    然后回答问题:

    请给出变化后的插入排序代码？ 请说明这种变化后，请支持新插入排序的算法复杂度？ 请说明这样是变快还是变慢了？ 答案：

    经过优化插入排序的复杂度仍然是O(n^2)，常数执行时间也几乎没有变化（其实省略了一次比较）但太微乎其微。因此，这个优化没有意义。

    1. function insert(A, i, x) {
    2.   let idx = bsearch(A,i,x)
    3.   let p = i - 1
    4.   while(p >= idx) {
    5.     A[p+1] = A[p]
    6.     p--
    7.   }
    8.   A[p + 1] = x
    9. }
    10. function insertion_sort(A){
    11.   for(let i = 1; i < A.length; i++) {
    12.     insert(A, i, A[i])
    13.   }
    14. }
    15. function bsearch(A, i, x){
    16.   let l = 0,
    17.       r = i-1,
    18.       guess
    20.   while(l<=r) {
    21.     guess = Math.floor( (l + r) / 2 )
    22.     if(A[guess] === x) return guess
    23.     if(A[guess] > x) {
    24.       if(guess === 0 || A[guess - 1] < x) {
    25.         return guess
    26.       }
    27.       r = guess - 1
    28.     } else {
    29.       if(guess === i-1 || A[guess + 1] > x) {
    30.         return guess + 1
    31.       }
    32.       l = guess + 1
    33.     }
    34.   }
    35. }