[GSoC status report] Week 6

[Teo Mrnjavac]

On Mon, Jun 1, 2009 at 2:18 PM, Seb Ruiz <ruiz at kde.org> wrote:
> 2009/6/1 Teo Mrnjavac <teo.mrnjavac at gmail.com>:
>> So I implemented kAdaptiveStableSort(),
>> a simple generic adaptive sorting algorithm that should perform close
>> to O(n) on a partially sorted input.
>
> I'm a little clueless on the entire situation here, but is it not
> possible to implement an O(nlogn) sorting algorithm to achieve the
> results that you want?
>
>
It totally is, but it might not be the best solution. In this case,
when a "small" number of tracks is added, there's a great degree of
presortedness in the list, this can be defined as a low number of
inversions in the list vs the sorted situation. Now, I could use an
optimal O(nlogn) algorithm, such as qStableSort() which implements
merge sort, but those don't take advantage of the presortedness - they
don't belong to the class of adaptive sort algorithms. So if I decide
to resort everything anyway I would probably define a threshold t,
hence if <t tracks have been added I use an adaptive sort such as
straight insertion sort and get performance close to O(n), and if >=t
tracks have been added I fall back to merge sort to avoid hitting
straight insertion's sort worst case O(n^2).