讨论内容不说明，仅提供相应的程序。

2.1:归并插入排序θ(nlgn)

void mergeInsertionSort(int a[], int l, int r, int k){    int m;    if(r-l+1 > k)    {        m = (l + r) / 2;        mergeInsertionSort(a, l, m, k);        mergeInsertionSort(a, m+1, r, k);        merge(a, l, m, r);    }    else if(l < r)        insertSort(a, l, r);}void insertSort(int a[], int l, int r){    int i, j, key;    j = l;    for(i=l+1; i<=r; i++)        if(a[i] < a[j]) j = i;    if(j > l)    {        key = a[j];        a[j] = a[l];        a[l] = key;    }    for(i=l+2; i<=r; i++)    {        key = a[i];        for(j=i-1; key

2.2:冒泡排序

void bubbleSort(int a[], int n){    int i, j, tmp;    for(i=0; i
      
       i; j--)            if(a[j] < a[j-1])            {                tmp = a[j];                a[j] = a[j-1];                a[j-1] = tmp;            }}
      

2.3: 多项式计算方法(θ(n))

int horner(int a[], int x, int n){    int i, sum=a[n-1];    for(i=n-2; i>=0; i--) sum = a[i] + x * sum;    return sum;}int polynomial(int a[], int x, int n){    int i, xArray[n], sum=0;    xArray[0] = 1;    for(i=1; i

 

2.4：计算数列的逆序θ(nlgn)

int mergeCount(int a[], int l, int r){    int m;    if(l < r)    {        m = (l + r) / 2;        return mergeCount(a, l, m) + mergeCount(a, m+1, r) + merge(a, l, m, r);    }    return 0;}int merge(int a[], int l, int m, int r){    int i, j, k, cnt=0;    int n1 = m - l + 1;    int n2 = r - m;    int lArray[n1+1], rArray[n2+1];    int max =10000;    for(i=0; i