basant307/AI_Governance_Project

1[![Build Status](https://travis-ci.org/kaelzhang/node-array-timsort.svg?branch=master)](https://travis-ci.org/kaelzhang/node-array-timsort)2[![Coverage](https://codecov.io/gh/kaelzhang/node-array-timsort/branch/master/graph/badge.svg)](https://codecov.io/gh/kaelzhang/node-array-timsort)3 4# array-timsort5 6A fork of [`timsort`](https://npmjs.org/package/timsort) with the following differences:7 8- `array-timsort` returns an array which records how the index of items have been sorted, while `timsort` returns `undefined`. See the example below.9- improves test coverage10- removes some dead code branches that could never be reached11- no longer built with UMD12 13```js14const {sort} = require('array-timsort')15 16const array = [3, 2, 1, 5]17 18sort(array)  // returns [2, 1, 0, 4]19 20console.log(array)  // [1, 2, 3, 5]21```22 23****24 25An adaptive and **stable** sort algorithm based on merging that requires fewer than nlog(n)26comparisons when run on partially sorted arrays. The algorithm uses O(n) memory and still runs in O(nlogn)27(worst case) on random arrays.28This implementation is based on the original29[TimSort](http://svn.python.org/projects/python/trunk/Objects/listsort.txt) developed30by Tim Peters for Python's lists (code [here](http://svn.python.org/projects/python/trunk/Objects/listobject.c)).31TimSort has been also adopted in Java starting from version 7.32 33## Acknowledgments34 35- @novacrazy: ported the module to ES6/ES7 and made it available via bower36- @kasperisager: implemented faster lexicographic comparison of small integers37 38## Usage39 40Install the package with npm:41 42```sh43npm i array-timsort44```45 46And use it:47 48```js49const {sort} = require('array-timsort')50 51const arr = [...]52 53sort(arr)54```55 56As `array.sort()` by default the `array-timsort` module sorts according to57lexicographical order.58 59You can also provide your own compare function (to sort any object) as:60 61```js62function numberCompare (a, b) {63    return a - b64}65 66const arr = [...]67 68sort(arr, numberCompare)69```70 71You can also sort only a specific subrange of the array:72 73```js74sort(arr, 5, 10)75sort(arr, numberCompare, 5, 10)76```77 78## Performance79 80A benchmark is provided in `benchmark/index.js`. It compares the `array-timsort` module against81the default `array.sort` method in the numerical sorting of different types of integer array82(as described [here](http://svn.python.org/projects/python/trunk/Objects/listsort.txt)):83 84-  *Random array*85-  *Descending array*86-  *Ascending array*87-  *Ascending array with 3 random exchanges*88-  *Ascending array with 10 random numbers in the end*89-  *Array of equal elements*90-  *Random Array with many duplicates*91-  *Random Array with some duplicates*92 93For any of the array types the sorting is repeated several times and for94different array sizes, average execution time is then printed.95I run the benchmark on Node v6.3.1 (both pre-compiled and compiled from source,96results are very similar), obtaining the following values:97 98<table>99  <tr>100    <th></th><th></th>101    <th colspan="2">Execution Time (ns)</th>102    <th rowspan="2">Speedup</th>103  </tr>104  <tr>105    <th>Array Type</th>106    <th>Length</th>107    <th>TimSort.sort</th>108    <th>array.sort</th>109  </tr>110<tbody>111 <tr>112  <td rowspan="4">Random</td><td>10</td><td>404</td><td>1583</td><td>3.91</td>113 </tr>114 <tr>115  <td>100</td><td>7147</td><td>4442</td><td>0.62</td>116 </tr>117 <tr>118  <td>1000</td><td>96395</td><td>59979</td><td>0.62</td>119 </tr>120 <tr>121  <td>10000</td><td>1341044</td><td>6098065</td><td>4.55</td>122 </tr>123 <tr>124  <td rowspan="4">Descending</td><td>10</td><td>180</td><td>1881</td><td>10.41</td>125 </tr>126 <tr>127  <td>100</td><td>682</td><td>19210</td><td>28.14</td>128</tr>129 <tr>130  <td>1000</td><td>3809</td><td>185185</td><td>48.61</td>131 </tr>132 <tr>133  <td>10000</td><td>35878</td><td>5392428</td><td>150.30</td>134 </tr>135 <tr>136  <td rowspan="4">Ascending</td><td>10</td><td>173</td><td>816</td><td>4.69</td>137 </tr>138 <tr>139  <td>100</td><td>578</td><td>18147</td><td>31.34</td>140 </tr>141 <tr>142  <td>1000</td><td>2551</td><td>331993</td><td>130.12</td>143 </tr>144 <tr>145  <td>10000</td><td>22098</td><td>5382446</td><td>243.57</td>146 </tr>147 <tr>148  <td rowspan="4">Ascending + 3 Rand Exc</td><td>10</td><td>232</td><td>927</td><td>3.99</td>149 </tr>150 <tr>151  <td>100</td><td>1059</td><td>15792</td><td>14.90</td>152 </tr>153 <tr>154  <td>1000</td><td>3525</td><td>300708</td><td>85.29</td>155 </tr>156 <tr>157  <td>10000</td><td>27455</td><td>4781370</td><td>174.15</td>158 </tr>159 <tr>160  <td rowspan="4">Ascending + 10 Rand End</td><td>10</td><td>378</td><td>1425</td><td>3.77</td>161 </tr>162 <tr>163  <td>100</td><td>1707</td><td>23346</td><td>13.67</td>164 </tr>165 <tr>166  <td>1000</td><td>5818</td><td>334744</td><td>57.53</td>167 </tr>168 <tr>169  <td>10000</td><td>38034</td><td>4985473</td><td>131.08</td>170 </tr>171 <tr>172  <td rowspan="4">Equal Elements</td><td>10</td><td>164</td><td>766</td><td>4.68</td>173 </tr>174 <tr>175  <td>100</td><td>520</td><td>3188</td><td>6.12</td>176 </tr>177 <tr>178  <td>1000</td><td>2340</td><td>27971</td><td>11.95</td>179 </tr>180 <tr>181  <td>10000</td><td>17011</td><td>281672</td><td>16.56</td>182 </tr>183 <tr>184  <td rowspan="4">Many Repetitions</td><td>10</td><td>396</td><td>1482</td><td>3.74</td>185 </tr>186 <tr>187  <td>100</td><td>7282</td><td>25267</td><td>3.47</td>188 </tr>189 <tr>190  <td>1000</td><td>105528</td><td>420120</td><td>3.98</td>191 </tr>192 <tr>193  <td>10000</td><td>1396120</td><td>5787399</td><td>4.15</td>194 </tr>195 <tr>196  <td rowspan="4">Some Repetitions</td><td>10</td><td>390</td><td>1463</td><td>3.75</td>197 </tr>198 <tr>199  <td>100</td><td>6678</td><td>20082</td><td>3.01</td>200 </tr>201 <tr>202  <td>1000</td><td>104344</td><td>374103</td><td>3.59</td>203 </tr>204 <tr>205  <td>10000</td><td>1333816</td><td>5474000</td><td>4.10</td>206 </tr>207</tbody>208</table>209 210`TimSort.sort` **is faster** than `array.sort` on almost of the tested array types.211In 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).212And also, in general, the bigger the array the more we benefit from using213the `array-timsort` module.214 215These 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:216```217npm run benchmark218```219Please also notice that:220 221-  This benchmark is far from exhaustive. Several cases are not considered222and the results must be taken as partial223-  *inlining* is surely playing an active role in `array-timsort` module's good performance224-  A more accurate comparison of the algorithms would require implementing `array.sort` in pure javascript225and counting element comparisons226 227## Stability228 229TimSort is *stable* which means that equal items maintain their relative order230after sorting. Stability is a desirable property for a sorting algorithm.231Consider the following array of items with an height and a weight.232```javascript233[234  { height: 100, weight: 80 },235  { height: 90, weight: 90 },236  { height: 70, weight: 95 },237  { height: 100, weight: 100 },238  { height: 80, weight: 110 },239  { height: 110, weight: 115 },240  { height: 100, weight: 120 },241  { height: 70, weight: 125 },242  { height: 70, weight: 130 },243  { height: 100, weight: 135 },244  { height: 75, weight: 140 },245  { height: 70, weight: 140 }246]247```248Items are already sorted by `weight`. Sorting the array249according to the item's `height` with the `array-timsort` module250results in the following array:251```javascript252[253  { height: 70, weight: 95 },254  { height: 70, weight: 125 },255  { height: 70, weight: 130 },256  { height: 70, weight: 140 },257  { height: 75, weight: 140 },258  { height: 80, weight: 110 },259  { height: 90, weight: 90 },260  { height: 100, weight: 80 },261  { height: 100, weight: 100 },262  { height: 100, weight: 120 },263  { height: 100, weight: 135 },264  { height: 110, weight: 115 }265]266```267Items with the same  `height` are still sorted by `weight` which means they preserved their relative order.268 269`array.sort`, instead, is not guarranteed to be *stable*. In Node v0.12.7270sorting the previous array by `height` with `array.sort` results in:271```javascript272[273  { height: 70, weight: 140 },274  { height: 70, weight: 95 },275  { height: 70, weight: 125 },276  { height: 70, weight: 130 },277  { height: 75, weight: 140 },278  { height: 80, weight: 110 },279  { height: 90, weight: 90 },280  { height: 100, weight: 100 },281  { height: 100, weight: 80 },282  { height: 100, weight: 135 },283  { height: 100, weight: 120 },284  { height: 110, weight: 115 }285]286```287As you can see the sorting did not preserve `weight` ordering for items with the288same `height`.289