[FFmpeg-devel] [PATCH 1/5] mxfdec: Parse IndexTableSegments and convert them into AVIndexEntry arrays

Michael Niedermayer michaelni at gmx.at
Fri Nov 18 15:34:03 CET 2011


On Fri, Nov 18, 2011 at 03:19:58PM +0100, Tomas Härdin wrote:
> On Mon, 2011-11-14 at 16:03 +0100, Michael Niedermayer wrote:
> > qsort() is O(n log(n)) for reverse order
> > qsort() breaks down to O(n^2) when elements are ordered

you sniped "so that the pivot always falls onto the maximum or minimum,"
which makes that quote quite confusing :)

qsort has no problem with increasing or decreasing order nor random
order, the problem exists when elements are sorted in a very
specific and implementation dependant way. the actual order might
look like if you reverse the bits of the indexes from normal order


> 
> Ah, I had it that it was the other way around. Anyway, not many entries.
> We can bother if someone finds a sample with tens of thousands of
> segments.

ill look at the patches in a moment

[....]
-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

The bravest are surely those who have the clearest vision
of what is before them, glory and danger alike, and yet
notwithstanding go out to meet it. -- Thucydides
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: Digital signature
URL: <http://ffmpeg.org/pipermail/ffmpeg-devel/attachments/20111118/c51e9114/attachment.asc>


More information about the ffmpeg-devel mailing list