[6a3a178] | 1 | # Node-TimSort: Fast Sorting for Node.js
|
---|
| 2 |
|
---|
| 3 | [![Build Status](https://travis-ci.org/mziccard/node-timsort.svg?branch=master)](https://travis-ci.org/mziccard/node-timsort)
|
---|
| 4 | [![npm version](https://badge.fury.io/js/timsort.svg)](https://www.npmjs.com/package/timsort)
|
---|
| 5 |
|
---|
| 6 | An adaptive and **stable** sort algorithm based on merging that requires fewer than nlog(n)
|
---|
| 7 | comparisons when run on partially sorted arrays. The algorithm uses O(n) memory and still runs in O(nlogn)
|
---|
| 8 | (worst case) on random arrays.
|
---|
| 9 | This implementation is based on the original
|
---|
| 10 | [TimSort](http://svn.python.org/projects/python/trunk/Objects/listsort.txt) developed
|
---|
| 11 | by Tim Peters for Python's lists (code [here](http://svn.python.org/projects/python/trunk/Objects/listobject.c)).
|
---|
| 12 | TimSort has been also adopted in Java starting from version 7.
|
---|
| 13 |
|
---|
| 14 | ## Acknowledgments
|
---|
| 15 |
|
---|
| 16 | - @novacrazy: ported the module to ES6/ES7 and made it available via bower
|
---|
| 17 | - @kasperisager: implemented faster lexicographic comparison of small integers
|
---|
| 18 |
|
---|
| 19 | ## Usage
|
---|
| 20 |
|
---|
| 21 | Install the package with npm:
|
---|
| 22 | ```
|
---|
| 23 | npm install --save timsort
|
---|
| 24 | ```
|
---|
| 25 | And use it:
|
---|
| 26 | ```javascript
|
---|
| 27 | var TimSort = require('timsort');
|
---|
| 28 |
|
---|
| 29 | var arr = [...];
|
---|
| 30 | TimSort.sort(arr);
|
---|
| 31 | ```
|
---|
| 32 | You can also install it with bower:
|
---|
| 33 | ```
|
---|
| 34 | bower install timsort
|
---|
| 35 | ```
|
---|
| 36 | As `array.sort()` by default the `timsort` module sorts according to
|
---|
| 37 | lexicographical order.
|
---|
| 38 | You can also provide your own compare function (to sort any object) as:
|
---|
| 39 | ```javascript
|
---|
| 40 | function numberCompare(a,b) {
|
---|
| 41 | return a-b;
|
---|
| 42 | }
|
---|
| 43 |
|
---|
| 44 | var arr = [...];
|
---|
| 45 | var TimSort = require('timsort');
|
---|
| 46 | TimSort.sort(arr, numberCompare);
|
---|
| 47 | ```
|
---|
| 48 | You can also sort only a specific subrange of the array:
|
---|
| 49 | ```javascript
|
---|
| 50 | TimSort.sort(arr, 5, 10);
|
---|
| 51 | TimSort.sort(arr, numberCompare, 5, 10);
|
---|
| 52 | ```
|
---|
| 53 |
|
---|
| 54 | ## Performance
|
---|
| 55 |
|
---|
| 56 | A benchmark is provided in `benchmark/index.js`. It compares the `timsort` module against
|
---|
| 57 | the default `array.sort` method in the numerical sorting of different types of integer array
|
---|
| 58 | (as described [here](http://svn.python.org/projects/python/trunk/Objects/listsort.txt)):
|
---|
| 59 |
|
---|
| 60 | - *Random array*
|
---|
| 61 | - *Descending array*
|
---|
| 62 | - *Ascending array*
|
---|
| 63 | - *Ascending array with 3 random exchanges*
|
---|
| 64 | - *Ascending array with 10 random numbers in the end*
|
---|
| 65 | - *Array of equal elements*
|
---|
| 66 | - *Random Array with many duplicates*
|
---|
| 67 | - *Random Array with some duplicates*
|
---|
| 68 |
|
---|
| 69 | For any of the array types the sorting is repeated several times and for
|
---|
| 70 | different array sizes, average execution time is then printed.
|
---|
| 71 | I run the benchmark on Node v6.3.1 (both pre-compiled and compiled from source,
|
---|
| 72 | results are very similar), obtaining the following values:
|
---|
| 73 |
|
---|
| 74 | <table>
|
---|
| 75 | <tr>
|
---|
| 76 | <th></th><th></th>
|
---|
| 77 | <th colspan="2">Execution Time (ns)</th>
|
---|
| 78 | <th rowspan="2">Speedup</th>
|
---|
| 79 | </tr>
|
---|
| 80 | <tr>
|
---|
| 81 | <th>Array Type</th>
|
---|
| 82 | <th>Length</th>
|
---|
| 83 | <th>TimSort.sort</th>
|
---|
| 84 | <th>array.sort</th>
|
---|
| 85 | </tr>
|
---|
| 86 | <tbody>
|
---|
| 87 | <tr>
|
---|
| 88 | <td rowspan="4">Random</td><td>10</td><td>404</td><td>1583</td><td>3.91</td>
|
---|
| 89 | </tr>
|
---|
| 90 | <tr>
|
---|
| 91 | <td>100</td><td>7147</td><td>4442</td><td>0.62</td>
|
---|
| 92 | </tr>
|
---|
| 93 | <tr>
|
---|
| 94 | <td>1000</td><td>96395</td><td>59979</td><td>0.62</td>
|
---|
| 95 | </tr>
|
---|
| 96 | <tr>
|
---|
| 97 | <td>10000</td><td>1341044</td><td>6098065</td><td>4.55</td>
|
---|
| 98 | </tr>
|
---|
| 99 | <tr>
|
---|
| 100 | <td rowspan="4">Descending</td><td>10</td><td>180</td><td>1881</td><td>10.41</td>
|
---|
| 101 | </tr>
|
---|
| 102 | <tr>
|
---|
| 103 | <td>100</td><td>682</td><td>19210</td><td>28.14</td>
|
---|
| 104 | </tr>
|
---|
| 105 | <tr>
|
---|
| 106 | <td>1000</td><td>3809</td><td>185185</td><td>48.61</td>
|
---|
| 107 | </tr>
|
---|
| 108 | <tr>
|
---|
| 109 | <td>10000</td><td>35878</td><td>5392428</td><td>150.30</td>
|
---|
| 110 | </tr>
|
---|
| 111 | <tr>
|
---|
| 112 | <td rowspan="4">Ascending</td><td>10</td><td>173</td><td>816</td><td>4.69</td>
|
---|
| 113 | </tr>
|
---|
| 114 | <tr>
|
---|
| 115 | <td>100</td><td>578</td><td>18147</td><td>31.34</td>
|
---|
| 116 | </tr>
|
---|
| 117 | <tr>
|
---|
| 118 | <td>1000</td><td>2551</td><td>331993</td><td>130.12</td>
|
---|
| 119 | </tr>
|
---|
| 120 | <tr>
|
---|
| 121 | <td>10000</td><td>22098</td><td>5382446</td><td>243.57</td>
|
---|
| 122 | </tr>
|
---|
| 123 | <tr>
|
---|
| 124 | <td rowspan="4">Ascending + 3 Rand Exc</td><td>10</td><td>232</td><td>927</td><td>3.99</td>
|
---|
| 125 | </tr>
|
---|
| 126 | <tr>
|
---|
| 127 | <td>100</td><td>1059</td><td>15792</td><td>14.90</td>
|
---|
| 128 | </tr>
|
---|
| 129 | <tr>
|
---|
| 130 | <td>1000</td><td>3525</td><td>300708</td><td>85.29</td>
|
---|
| 131 | </tr>
|
---|
| 132 | <tr>
|
---|
| 133 | <td>10000</td><td>27455</td><td>4781370</td><td>174.15</td>
|
---|
| 134 | </tr>
|
---|
| 135 | <tr>
|
---|
| 136 | <td rowspan="4">Ascending + 10 Rand End</td><td>10</td><td>378</td><td>1425</td><td>3.77</td>
|
---|
| 137 | </tr>
|
---|
| 138 | <tr>
|
---|
| 139 | <td>100</td><td>1707</td><td>23346</td><td>13.67</td>
|
---|
| 140 | </tr>
|
---|
| 141 | <tr>
|
---|
| 142 | <td>1000</td><td>5818</td><td>334744</td><td>57.53</td>
|
---|
| 143 | </tr>
|
---|
| 144 | <tr>
|
---|
| 145 | <td>10000</td><td>38034</td><td>4985473</td><td>131.08</td>
|
---|
| 146 | </tr>
|
---|
| 147 | <tr>
|
---|
| 148 | <td rowspan="4">Equal Elements</td><td>10</td><td>164</td><td>766</td><td>4.68</td>
|
---|
| 149 | </tr>
|
---|
| 150 | <tr>
|
---|
| 151 | <td>100</td><td>520</td><td>3188</td><td>6.12</td>
|
---|
| 152 | </tr>
|
---|
| 153 | <tr>
|
---|
| 154 | <td>1000</td><td>2340</td><td>27971</td><td>11.95</td>
|
---|
| 155 | </tr>
|
---|
| 156 | <tr>
|
---|
| 157 | <td>10000</td><td>17011</td><td>281672</td><td>16.56</td>
|
---|
| 158 | </tr>
|
---|
| 159 | <tr>
|
---|
| 160 | <td rowspan="4">Many Repetitions</td><td>10</td><td>396</td><td>1482</td><td>3.74</td>
|
---|
| 161 | </tr>
|
---|
| 162 | <tr>
|
---|
| 163 | <td>100</td><td>7282</td><td>25267</td><td>3.47</td>
|
---|
| 164 | </tr>
|
---|
| 165 | <tr>
|
---|
| 166 | <td>1000</td><td>105528</td><td>420120</td><td>3.98</td>
|
---|
| 167 | </tr>
|
---|
| 168 | <tr>
|
---|
| 169 | <td>10000</td><td>1396120</td><td>5787399</td><td>4.15</td>
|
---|
| 170 | </tr>
|
---|
| 171 | <tr>
|
---|
| 172 | <td rowspan="4">Some Repetitions</td><td>10</td><td>390</td><td>1463</td><td>3.75</td>
|
---|
| 173 | </tr>
|
---|
| 174 | <tr>
|
---|
| 175 | <td>100</td><td>6678</td><td>20082</td><td>3.01</td>
|
---|
| 176 | </tr>
|
---|
| 177 | <tr>
|
---|
| 178 | <td>1000</td><td>104344</td><td>374103</td><td>3.59</td>
|
---|
| 179 | </tr>
|
---|
| 180 | <tr>
|
---|
| 181 | <td>10000</td><td>1333816</td><td>5474000</td><td>4.10</td>
|
---|
| 182 | </tr>
|
---|
| 183 | </tbody>
|
---|
| 184 | </table>
|
---|
| 185 |
|
---|
| 186 | `TimSort.sort` **is faster** than `array.sort` on almost of the tested array types.
|
---|
| 187 | In general, the more ordered the array is the better `TimSort.sort` performs with respect to `array.sort` (up to 243 times faster on already sorted arrays).
|
---|
| 188 | And also, in general, the bigger the array the more we benefit from using
|
---|
| 189 | the `timsort` module.
|
---|
| 190 |
|
---|
| 191 | These data strongly depend on Node.js version and the machine on which the benchmark is run. I strongly encourage you to run the benchmark on your own setup with:
|
---|
| 192 | ```
|
---|
| 193 | npm run benchmark
|
---|
| 194 | ```
|
---|
| 195 | Please also notice that:
|
---|
| 196 |
|
---|
| 197 | - This benchmark is far from exhaustive. Several cases are not considered
|
---|
| 198 | and the results must be taken as partial
|
---|
| 199 | - *inlining* is surely playing an active role in `timsort` module's good performance
|
---|
| 200 | - A more accurate comparison of the algorithms would require implementing `array.sort` in pure javascript
|
---|
| 201 | and counting element comparisons
|
---|
| 202 |
|
---|
| 203 | ## Stability
|
---|
| 204 |
|
---|
| 205 | TimSort is *stable* which means that equal items maintain their relative order
|
---|
| 206 | after sorting. Stability is a desirable property for a sorting algorithm.
|
---|
| 207 | Consider the following array of items with an height and a weight.
|
---|
| 208 | ```javascript
|
---|
| 209 | [
|
---|
| 210 | { height: 100, weight: 80 },
|
---|
| 211 | { height: 90, weight: 90 },
|
---|
| 212 | { height: 70, weight: 95 },
|
---|
| 213 | { height: 100, weight: 100 },
|
---|
| 214 | { height: 80, weight: 110 },
|
---|
| 215 | { height: 110, weight: 115 },
|
---|
| 216 | { height: 100, weight: 120 },
|
---|
| 217 | { height: 70, weight: 125 },
|
---|
| 218 | { height: 70, weight: 130 },
|
---|
| 219 | { height: 100, weight: 135 },
|
---|
| 220 | { height: 75, weight: 140 },
|
---|
| 221 | { height: 70, weight: 140 }
|
---|
| 222 | ]
|
---|
| 223 | ```
|
---|
| 224 | Items are already sorted by `weight`. Sorting the array
|
---|
| 225 | according to the item's `height` with the `timsort` module
|
---|
| 226 | results in the following array:
|
---|
| 227 | ```javascript
|
---|
| 228 | [
|
---|
| 229 | { height: 70, weight: 95 },
|
---|
| 230 | { height: 70, weight: 125 },
|
---|
| 231 | { height: 70, weight: 130 },
|
---|
| 232 | { height: 70, weight: 140 },
|
---|
| 233 | { height: 75, weight: 140 },
|
---|
| 234 | { height: 80, weight: 110 },
|
---|
| 235 | { height: 90, weight: 90 },
|
---|
| 236 | { height: 100, weight: 80 },
|
---|
| 237 | { height: 100, weight: 100 },
|
---|
| 238 | { height: 100, weight: 120 },
|
---|
| 239 | { height: 100, weight: 135 },
|
---|
| 240 | { height: 110, weight: 115 }
|
---|
| 241 | ]
|
---|
| 242 | ```
|
---|
| 243 | Items with the same `height` are still sorted by `weight` which means they preserved their relative order.
|
---|
| 244 |
|
---|
| 245 | `array.sort`, instead, is not guarranteed to be *stable*. In Node v0.12.7
|
---|
| 246 | sorting the previous array by `height` with `array.sort` results in:
|
---|
| 247 | ```javascript
|
---|
| 248 | [
|
---|
| 249 | { height: 70, weight: 140 },
|
---|
| 250 | { height: 70, weight: 95 },
|
---|
| 251 | { height: 70, weight: 125 },
|
---|
| 252 | { height: 70, weight: 130 },
|
---|
| 253 | { height: 75, weight: 140 },
|
---|
| 254 | { height: 80, weight: 110 },
|
---|
| 255 | { height: 90, weight: 90 },
|
---|
| 256 | { height: 100, weight: 100 },
|
---|
| 257 | { height: 100, weight: 80 },
|
---|
| 258 | { height: 100, weight: 135 },
|
---|
| 259 | { height: 100, weight: 120 },
|
---|
| 260 | { height: 110, weight: 115 }
|
---|
| 261 | ]
|
---|
| 262 | ```
|
---|
| 263 | As you can see the sorting did not preserve `weight` ordering for items with the
|
---|
| 264 | same `height`.
|
---|