Unreviewed, rolling out r234489.
[WebKit-https.git] / Source / WTF / wtf / BubbleSort.h
1 /*
2  * Copyright (C) 2015 Apple Inc. All Rights Reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #ifndef BubbleSort_h
27 #define BubbleSort_h
28
29 namespace WTF {
30
31 // Why would you want to use bubble sort? When you know that your input is already mostly
32 // sorted! This sort is guaranteed stable (it won't reorder elements that were equal), it
33 // doesn't require any scratch memory, and is the fastest available sorting algorithm if your
34 // input already happens to be sorted. This sort is also likely to have competetive performance
35 // for small inputs, even if they are very unsorted.
36
37 // We use this sorting algorithm for compiler insertion sets. An insertion set is usually very
38 // nearly sorted. It shouldn't take more than a few bubbles to make it fully sorted. We made
39 // this decision deliberately. Here's the performance of the testb3 Complex(64, 384) benchmark
40 // with the Air::InsertionSet doing no sorting, std::stable_sorting, and bubbleSorting:
41 //
42 // no sort:          8.8222 +- 0.1911 ms.
43 // std::stable_sort: 9.0135 +- 0.1418 ms.
44 // bubbleSort:       8.8457 +- 0.1511 ms.
45 //
46 // Clearly, bubble sort is superior.
47 //
48 // Note that the critical piece here is that insertion sets tend to be small, they must be
49 // sorted, the sort must be stable, they are usually already sorted to begin with, and when they
50 // are unsorted it's usually because of a few out-of-place elements.
51
52 template<typename IteratorType, typename LessThan>
53 void bubbleSort(IteratorType begin, IteratorType end, const LessThan& lessThan)
54 {
55     for (;;) {
56         bool changed = false;
57         ASSERT(end >= begin);
58         size_t limit = end - begin;
59         for (size_t i = limit; i-- > 1;) {
60             if (lessThan(begin[i], begin[i - 1])) {
61                 std::swap(begin[i], begin[i - 1]);
62                 changed = true;
63             }
64         }
65         if (!changed)
66             return;
67         // After one run, the first element in the list is guaranteed to be the smallest.
68         begin++;
69
70         // Now go in the other direction. This eliminates most sorting pathologies.
71         changed = false;
72         ASSERT(end >= begin);
73         limit = end - begin;
74         for (size_t i = 1; i < limit; ++i) {
75             if (lessThan(begin[i], begin[i - 1])) {
76                 std::swap(begin[i], begin[i - 1]);
77                 changed = true;
78             }
79         }
80         if (!changed)
81             return;
82         // Now the last element is guaranteed to be the largest.
83         end--;
84     }
85 }
86
87 template<typename IteratorType>
88 void bubbleSort(IteratorType begin, IteratorType end)
89 {
90     bubbleSort(
91         begin, end,
92         [](auto& left, auto& right) {
93             return left < right;
94         });
95 }
96
97 } // namespace WTF
98
99 using WTF::bubbleSort;
100
101 #endif // BubbleSort_h
102