<div dir="ltr"><div>This describes an optimization for "binary insertion sort" (BINSORT for short).</div><div><br></div><div>BINSORT has been implemented in Python, CyThon, and Timsort (the default Array.sort() in JAVA SE 7 and JAVA SE 8)</div><div>I have read the BINSORT in Timsort</div><div> <a href="http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8-b132/java/util/TimSort.java#TimSort.binarySort%28java.lang.Object%5B%5D%2Cint%2Cint%2Cint%2Cjava.util.Comparator%29">http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8-b132/java/util/TimSort.java#TimSort.binarySort%28java.lang.Object%5B%5D%2Cint%2Cint%2Cint%2Cjava.util.Comparator%29</a></div><div>and I think that I can make a little more optimization.</div><div><br></div><div>=================</div><div>The old BINSORT:</div><div><span class="" style="white-space:pre">       </span>The basic idea is to use binary search on the sorted list to find a final position</div><div><span class="" style="white-space:pre"> </span>for a new element X, then insert X to the sorted list.</div><div><span class="" style="white-space:pre">     </span></div><div><span class="" style="white-space:pre">   </span>[SORTED_LIST], [X in UNSORTED_LIST]  // pick X in UNSORTED_LIST</div><div><span class="" style="white-space:pre">   </span>index = binarySeach([SORTED_LIST])<span class="" style="white-space:pre">        </span>// use binary search to find appropriate location for X in SORTED_LIST</div><div><span class="" style="white-space:pre">     </span>[SORTED_LIST].add(index, X) // insert X to index location</div><div><br></div><div>==================</div><div>New BINSORT:</div><div><span class="" style="white-space:pre">     </span>[SORTED_LIST], [A]  // A is an UNSORTED_LIST</div><div><span class="" style="white-space:pre">      </span>j = compare(A[i], A[i+1]) // pick A[i], compare to next element</div><div><span class="" style="white-space:pre">    </span>index = binarySeach([SORTED_LIST], A[i])  // use binary search to find </div><div><span class="" style="white-space:pre">                                                                                  </span>  // appropriate location for A[i] in SORTED_LIST, and remember the index</div><div><span class="" style="white-space:pre"> </span>[SORTED_LIST].add(index, A[i]) // insert A[i] to index location</div><div><span class="" style="white-space:pre">    </span></div><div><span class="" style="white-space:pre">   </span>// Now for A[+1], where already know where it should be, compare to A[i]</div><div><span class="" style="white-space:pre">   </span>if j >= 0:</div><div><span class="" style="white-space:pre">              </span>// A[i] > A[i+1], so A[i+1] will be in the right side of A[i]</div><div><span class="" style="white-space:pre">           </span>// We only have to search on a reduced Array:</div><div><span class="" style="white-space:pre">              </span>index = binarySearch(SORTED_LIST[index : length(SORTED_LIST)], A[i+1])</div><div><span class="" style="white-space:pre">     </span>else:</div><div><span class="" style="white-space:pre">              </span>// we search on the left side of of A[i]</div><div><span class="" style="white-space:pre">           </span>index = binarySearch(SORTED_LIST[0 : index], A[i+1])</div><div><span class="" style="white-space:pre">       </span>[SORTED_LIST].add(index, A[i+1]) // insert A[i+1] to index location</div><div><span class="" style="white-space:pre">        </span></div><div><span class="" style="white-space:pre">   </span>//repeat the loop</div><div><span class="" style="white-space:pre">  </span></div><div>==================</div><div>Run test.</div><div>Intuitively, new BINSORT will be better if the Array become bigger, because</div><div>it reduce the array to search with the cost of only 1 more comparison.</div><div><br></div><div>I only care about small array, with the length < 100 (we have known that in Timsort, the</div><div>list is divided to chunks with length 64, then apply BINSORT to them).</div><div><br></div><div>So I make a big Array, divide them, and apply new BINSORT in each chunk, then compare to OLD BINSORT.</div><div>The source code is in the bottom of this document. Here is the results:</div><div><br></div><div>cpuinfo:</div><div>model name      : Intel(R) Core(TM) i3 CPU       M 350  @ 2.27GHz</div><div>stepping        : 2</div><div>microcode       : 0xc</div><div>cpu MHz         : 933.000</div><div>cache size      : 3072 KB</div><div>-----</div><div><br></div><div>random array:</div><div>ARRAY_SIZE: 1000000</div><div>CHUNK_SIZE: 100</div><div>DATA: randint(0, 1000000)</div><div><br></div><div>OLD BINSORT: 81.45754</div><div>new BINSORT: 5.26754</div><div>RATIO: (OLD - new) / new = 14.464</div><div>---</div><div>incremental array:</div><div>ARRAY_SIZE: 1000000</div><div>CHUNK_SIZE: 100</div><div>DATA: range(0, 1000000)<span class="" style="white-space:pre">  </span></div><div><br></div><div>OLD BINSORT: 81.87927</div><div>new BINSORT: 5.41651</div><div>RATIO: (OLD - new) / new = 14.11659</div><div>---</div><div>decremental array:</div><div>ARRAY_SIZE: 1000000</div><div>CHUNK_SIZE: 100</div><div>DATA: range(0, 1000000)</div><div><br></div><div>OLD BINSORT: 81.45723</div><div>new BINSORT: 5.09823</div><div>RATIO: (OLD - new) / new = 14.97753</div><div>----</div><div>all equal array:</div><div>ARRAY_SIZE: 1000000</div><div>CHUNK_SIZE: 100</div><div>DATA: 50000</div><div><br></div><div>OLD BINSORT: 40.46027</div><div>new BINSORT: 5.41221</div><div>RATIO: (OLD - new) / new = 6.47573</div><div><br></div><div>====================</div><div>What should we do next:</div><div><span class="" style="white-space:pre">       </span>- Tuning my test code (I have just graphed it).</div><div><span class="" style="white-space:pre">    </span>- Test other cases, and bigger array (my laptop cannot handle array more than 10^6.)</div><div><span class="" style="white-space:pre">       </span>- Modifying Timsort in java.util. and test if it is better.</div><div><br></div><div>====================</div><div>My test code, written by Python.  </div><div><br></div><div>from timeit import Timer</div><div><br></div><div>setup ="""\</div><div>import bisect</div><div>from random import randint</div><div>from timeit import Timer</div><div>SIZE = 1000000</div><div>CHUNK = 100</div><div>NUM_CHUNK = SIZE/CHUNK</div><div>data = []</div><div>data2 = []</div><div>data3 = []</div><div>for i in range(0,SIZE):</div><div>    data.append(randint(0,1000000))</div><div>    #data.append(i)</div><div>#data = data[::-1]</div><div>"""</div><div>sample ="""\</div><div>for j in range(0,NUM_CHUNK):</div><div>    low =  CHUNK*j</div><div>    high=  low + CHUNK</div><div>    data2.append(data[low])</div><div>    index = low</div><div>    for i in range(low,high):</div><div>        x = data[i]</div><div>        index = bisect.bisect_right(data2[low:], x, low, len(data2) - low-1)</div><div>        data2.insert(index, x)</div><div>"""</div><div><br></div><div>new ="""\</div><div>for j in range(0,NUM_CHUNK):</div><div>    low =  CHUNK*j</div><div>    high=  low + CHUNK</div><div>    data3.append(data[low])</div><div>    index = low</div><div>    for i in range(low,high):</div><div>        x = data[i]</div><div>        if x >= data[i-1]:</div><div>            index = bisect.bisect_right(data3[low:len(data3) - low-1], x, index, len(data3) - low-1)</div><div>        else:</div><div>            index = bisect.bisect_right(data3[low:index], x, low, index)</div><div>        data3.insert(index, x)</div><div>"""</div><div>t2 = Timer(stmt = sample, setup=setup)</div><div>a = t2.timeit(1)</div><div>print a</div><div>t3 = Timer(stmt = new, setup=setup)</div><div>b = t3.timeit(1)</div><div>print b</div><div>print (str((a - b)/b))</div><div><br></div><div>====================================</div><div><br></div><div>Nha Pham</div><div>Mar 07 2015</div></div>