自然的归并排序

这道题是用自底向上的归并排序，要利用子数组的有序性。我们要先找到两个有序的子数组，将其归并后，再往后寻找下一个有序的子数组，与前面归并后的数组再次归并：

// 原地归并
public static void merge(Comparable[] a, int lo, int mid, int hi)
{
    // 将a[lo..mid]和a[mid+1..hi]归并
    int i = lo, j = mid + 1;

    //Comparable[] aux = new Comparable[a.length];
    Comparable[] aux = new Comparable[a.length];
    // 将a[lo..hi]复制到aux[lo..hi]
    for (int k = lo; k <= hi; k++)
    {
        aux[k] = a[k];
    }

    // 归并回到a[lo..hi]
    for (int k = lo; k <= hi; k++)
    {
        if (i > mid) {
            a[k] = aux[j++];
        } else if (j > hi) {
            a[k] = aux[i++];
        } else if (less(aux[j], aux[i])) {
            a[k] = aux[j++];
        } else {
            a[k] = aux[i++];
        }
    }

    StdOut.println();
    //StdOut.println("hi: " + hi + ", lo: " + lo);
}

public static void sort(Comparable[] a)
{
    int n = a.length;
    int lo = 0;
    int mid = -1;
    int hi = -1;

    while (hi < n - 1)
    {
        for (int i = hi + 1; i < n; i++)
        {
            if ((i + 1) < a.length)
            {
                if (!less(a[i], a[i + 1])) {
                    if (mid == -1) {
                        mid = i;
                    } else {
                        hi = i;
                        break;
                    }
                }
            }
            else // 已到末尾
            {
                if (mid == -1) {
                    mid = i;
                }
                hi = i;
            }
        }
        if (mid != hi) {
            merge(a, lo, mid, hi);
            StdOut.println("mid: " + mid + ", hi: " + hi);
        }

        mid = hi;
    }

    StdOut.println();
}

主要是sort方法，lo表示其实索引，mid表示中间索引，hi表示末尾索引。

int n = a.length;
int lo = 0;
int mid = -1;
int hi = -1;

在第一次循环时，确定mid，hi，确定hi后，跳出循环：

for (int i = hi + 1; i < n; i++)
{
    if ((i + 1) < a.length)
    {
        if (!less(a[i], a[i + 1])) {
            if (mid == -1) {
                mid = i;
            } else {
                hi = i;
                break;
            }
        }
    }
    else // 已到末尾
    {
        if (mid == -1) {
            mid = i;
        }
        hi = i;
    }
}

后续的mid在每次的while循环中，设置等于上一次的hi，当mid等于hi时，表示已经是有序的了，不用归并。

while (hi < n - 1)
{
    for (int i = hi + 1; i < n; i++)
    {
        if ((i + 1) < a.length)
        {
            if (!less(a[i], a[i + 1])) {
                if (mid == -1) {
                    mid = i;
                } else {
                    hi = i;
                    break;
                }
            }
        }
        else // 已到末尾
        {
            if (mid == -1) {
                mid = i;
            }
            hi = i;
        }
    }
    if (mid != hi) {
        merge(a, lo, mid, hi);
        StdOut.println("mid: " + mid + ", hi: " + hi);
    }

    mid = hi;
}

至于【根据数组大小和数组中递增的子数组的最大长度分析算法运行时间】：

前面已排序的子数组的大小越大，所需时间也越长。

O(nLogn)。

对于时间复杂度，我还不是特别清楚。