[Tim]
>> 1. Merge "2 at a time" instead of just 1. That is, first "sort" the
>> next 2 elements to be merged (1 compare and a possible swap). Then
>> binary search to find where the smaller belongs, and a shorter binary
>> search to find where the larger belongs. Then shift both into place.
[Ar
Hi Tim,
On 10 March 2015 at 18:22, Tim Peters wrote:
> 1. Merge "2 at a time" instead of just 1. That is, first "sort" the
> next 2 elements to be merged (1 compare and a possible swap). Then
> binary search to find where the smaller belongs, and a shorter binary
> search to find where the larg
OK - here's what the current binsort does, ignoring that it skips an
already-sorted prefix (if any), and creating a new list instead of
modifying in-place:
def oldsort(a):
from bisect import bisect_right as br
assert a
result = [a[0]]
for i in range(1, len(a)):
[nha pham ]
> Thank you very much. I am very happy that I got a reply from Tim Peter.
My pleasure to speak with you too :-)
> You are correct, my mistake.
>
> The python code should be:
> for i in range(low+1,high): //because we already add
> data[low]
> x = data[i]
>
Thank you very much. I am very happy that I got a reply from Tim Peter.
You are correct, my mistake.
The python code should be:
for i in range(low+1,high): //because we already add
data[low]
x = data[i]
if x >= data[i-1]:
After I fix it, here is the result:
rand
[nha pham ]
> Statement_1: With an array of size N or less than N, we need at most log2(N)
> comparisons to find a value
> (or a position, incase the search miss), using the binary search algorithm.
>
> proof: This statement is trivia, and I believe, someone outthere already
> proved it.
Sorry for
Thank you for your comment. I admit that I did not thinking about the proof
before.
Here is my naive proof. I hope you can give me some comments:
=
# This proof is an empirical thinking and is not completed, it just gives
us a closer look.
I hope someone can make it more mathematically
It may be that the comparison that you do is between two elements that are
almost always in the same cache line whereas the binary search might often
incur a cache miss.
On Mon, Mar 9, 2015 at 2:49 PM, nha pham wrote:
> I do not know exactly, one thing I can imagine is: it turns the worst case
>
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 the
smallest or the the highest of the sor
On 15-03-08, nha pham
wrote:
>
> 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.
On Mon, Mar 9, 2015 at 10:53 AM, Steven D'Aprano wrote:
> On Sun, Mar 08, 2015 at 10:57:30PM -0700, Ryan Smith-Roberts wrote:
>> I suspect that you will find the Python community extremely conservative
>> about any changes to its sorting algorithm, given that it took thirteen
>> years and some rea
On Sun, Mar 08, 2015 at 10:57:30PM -0700, Ryan Smith-Roberts wrote:
> I suspect that you will find the Python community extremely conservative
> about any changes to its sorting algorithm, given that it took thirteen
> years and some really impressive automated verification software to find
> this
I suspect that you will find the Python community extremely conservative
about any changes to its sorting algorithm, given that it took thirteen
years and some really impressive automated verification software to find
this bug:
http://envisage-project.eu/proving-android-java-and-python-sorting-alg
On 3/8/2015 8:17 PM, nha pham wrote:
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 sugge
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
15 matches
Mail list logo
