LawrencePeng's Blog

专注收集代码小精灵

Natural Mergesort

  • 目的

    • 普通MergeSort对于原本有序或者接近有序的数组的表现不好，所以引出了Natural Mergesort。

  • 过程

    • 和MergeSort自顶向下的过程不同，Natural Mergesort选择了相反的方向。

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    ForwardIterator SortedRangeEnd(ForwardIterator begin, ForwardIterator end, Comparator comp) {
        /* Edge case - if the input is empty, we're done. */
        if (begin == end) return end;
        /* Get an iterator that's one step ahead of begin. */
        ForwardIterator next = begin; ++next;
        /* Keep marching these iterators forward until we find a mismatch or
         * hit the end.  A mismatch occurs when the element after the current
         * is strictly less than the current element.
         */
        for (; next != end && !comp(*next, *begin); ++next, ++begin)
          ;
        /* The above loop stops either when next is the end of the sequence or
         * when next is the crossover point.  In either case, return next.
         */
        return next;
      }

这个函数是来找到已经排好序的范围。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void Merge(ForwardIterator begin, ForwardIterator mid,
             ForwardIterator end, Comparator comp) {
    /* Determine the type of the element being iterated over. */
    typedef typename std::iterator_traits<ForwardIterator>::value_type T;
    /* Create a vector of Ts that will hold the merged sequence. */
    std::vector<T> merge;
    /* Continuously choose the smaller of the two to go in front until some
     * range is consumed.
     */
    ForwardIterator one = begin, two = mid;
    while (one != mid && two != end) {
      if (comp(*one, *two)) { // First sequence has smaller element
        merge.push_back(*one);
        ++one;
      } else { // Second sequence has smaller element.
        merge.push_back(*two);
        ++two;
      }
    }
    /* Once one of the sequences has been exhausted, one of two cases holds:
     *
     * 1. The first sequence was consumed.  In that case, the rest of the
     *    second sequence is valid and we can just copy the merged sequence
     *    in front of it.
     * 2. The second sequence was consumed.  In that case, we copy the rest
     *    of the first sequence into the merged sequence, then write the
     *    merged sequence back.
     */
    if (two == end)
      merge.insert(merge.end(), one, mid);
    std::copy(merge.begin(), merge.end(), begin);
  }

稀疏平常的merge部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
NaturalMergesort(ForwardIterator begin, ForwardIterator end,
                      Comparator comp) {
if (begin == end) return;
  /* Track whether the current iteration of the algorithm has made any
   * changes.  If it didn't, then we can finish early.
   */
  bool haveMerged;
  /* Continuously loop, merging together ranges until the input is fully
   * sorted.
   */
  do {
    /* We have not yet merged anything, so clear this flag. */
    haveMerged = false;
    /* Scan forward in the loop, looking for adjacent pairs of sorted ranges
     * and merging them.  
     */
    for (ForwardIterator itr = begin; itr != end; ) {
      /* See how far this range extends. */
      ForwardIterator rangeEnd = SortedRangeEnd(itr, end, comp);
      /* If we hit the end of the range, we're done with this iteration. */
      if (rangeEnd == end) break;
      /* See where the end of that range is. */
      ForwardIterator nextRangeEnd = SortedRangeEnd(rangeEnd, end, comp);
      /* Merge this range with the range after it. */
      Merge(itr, rangeEnd, nextRangeEnd, comp);
      
      /* Flag that we did at least one merge so we don't stop early. */
      haveMerged = true;
      /* Advance the iterator to the start of the next sequence, which is
       * directly after the end of the second sorted range.
       */
      itr = nextRangeEnd;
    }
  } while (haveMerged);
}

可以看到只是一个很小的更改，就能让我们成功降低mergesort最好时间复杂度，真正让mergesort更加实用了。

Algo