On Wed, Oct 23, 2013 at 2:45 PM, Adrien Grand <jpou...@gmail.com> wrote:
> Hi, > > On Wed, Oct 23, 2013 at 10:19 PM, Arvind Kalyan <bas...@gmail.com> wrote: > > Sorting is not an option for our case so we will most likely implement a > > variant that merges the segments in one pass. Using TimSort is great but > in > > our case the 2 segments will be highly interspersed and would not benefit > > from the galloping in TimSort. > > I think Shai didn't mention TimSort because of galloping, but because > it tries to discover the monotonic sequences in your data. In your > particular case, this means that the sorting would run in linear time > instead of O(n log(n)) given that the 2 segments to merge are sorted. > OK, I went back and read about TimSort and it does appear to be optimized for this use-case. Apologize for my ignorance :-) I will benchmark the available approach itself then, in that case. Will revert back if the performance in unacceptable. Thanks.
