讨论内容不说明，仅提供相应的程序。
2.1:归并插入排序θ(nlgn)
void mergeInsertionSort(int a[], int l, int r, int k)
{
int m;
if(r-l+ > k)
{
m = (l + r) / ;
mergeInsertionSort(a, l, m, k);
mergeInsertionSort(a, m+, 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+; 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+; i<=r; i++)
{
key = a[i];
for(j=i-; key<a[j]; j--) a[j+] = a[j];
a[j+] = key;
}
} void merge(int a[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + ;
int n2 = r - m;
int lArray[n1+], rArray[n2+];
int max = ; for(i=; i<n1; i++) lArray[i] = a[l+i];
for(i=; i<n2; i++) rArray[i] = a[m+i+];
lArray[n1] = max;
rArray[n2] = max;
i = ;
j = ;
for(k=l; k<=r; k++)
{
if(lArray[i] <= rArray[j])
{
a[k] = lArray[i];
++i;
}
else
{
a[k] = rArray[j];
++j;
}
}
}
2.2:冒泡排序
void bubbleSort(int a[], int n)
{
int i, j, tmp; for(i=; i<n-; i++)
for(j=n-; j>i; j--)
if(a[j] < a[j-])
{
tmp = a[j];
a[j] = a[j-];
a[j-] = tmp;
}
}
2.3: 多项式计算方法(θ(n))
int horner(int a[], int x, int n)
{
int i, sum=a[n-];
for(i=n-; i>=; i--) sum = a[i] + x * sum;
return sum;
} int polynomial(int a[], int x, int n)
{
int i, xArray[n], sum=;
xArray[] = ;
for(i=; i<n; i++) xArray[i] = x * xArray[i-];
for(i=; i<n; i++) sum = sum + a[i] * xArray[i];
return sum;
}
2.4：计算数列的逆序θ(nlgn)
int mergeCount(int a[], int l, int r)
{
int m;
if(l < r)
{
m = (l + r) / ;
return mergeCount(a, l, m) + mergeCount(a, m+, r) + merge(a, l, m, r);
}
return ;
} int merge(int a[], int l, int m, int r)
{
int i, j, k, cnt=;
int n1 = m - l + ;
int n2 = r - m;
int lArray[n1+], rArray[n2+];
int max =; for(i=; i<n1; i++) lArray[i] = a[l+i];
for(j=; j<n2; j++) rArray[j] = a[m++j];
lArray[n1] = max;
rArray[n2] = max;
i = ;
j = ;
for(k=l; k<=r; k++)
if(lArray[i] <= rArray[j])
{
a[k] = lArray[i];
++i;
}
else
{
a[k] = rArray[j];
cnt += (m + j - k + );
++j;
}
return cnt;
}