nto the
timeit.Timer class. I am pretty sure about this.
I will try to write the proof more clearly, sorry for inconvenience.
Thank you very much.
Nha Pham.
On Mon, Mar 9, 2015 at 9:27 PM, Tim Peters wrote:
> [nha pham ]
> > Statement_1: With an array of size N or less than N, we
I have something more, I will update my proof at:
https://github.com/nhapq/Optimize_binary_insertion_sort/blob/master/proof.txt
==
Thank you.
Nha Pham.
On Mon, Mar 9, 2015 at 10:39 AM, Isaac Schwabacher
wrote:
> On 15-03-08, nha pham
> wrote:
> >
> > We can optimize the TimSort algo
, nha pham wrote:
> I do not know exactly, one thing I can imagine is: it turns the worst case
> of binary insertion sort to best case.
> With sorted array in range of 32 or 64 items, built from zero element. The
> new element you put into the sorted list has a high chance of being th
We can optimize the TimSort algorithm by optimizing its binary insertion
sort.
The current version of binary insertion sort use this idea:
Use binary search to find a final position in sorted list for a new element
X. Then insert X to that location.
I suggest another idea:
Use binary search
x = bisect.bisect_right(data3[low:len(data3) - low-1], x,
index, len(data3) - low-1)
else:
index = bisect.bisect_right(data3[low:index], x, low, index)
data3.insert(index, x)
"""
t2 = Timer(stmt = sample, setup=setup)
a = t2.timeit(1)
print a
t3 = Timer(stmt = new,
