search

IanYates / pdfium

Automatically exported from code.google.com/p/pdfium
0 stars 0 forks source link

CGW_ArrayTemplate::QuickSort() isn't very quick #72

Open GoogleCodeExporter opened 9 years ago

GoogleCodeExporter commented 9 years ago 
Found by inspection.  In fact, it looks to be O(n^2 log n).  The problem is the 
way that out of place elements are swapped:

                this->InsertAt(m+1, temp);
                this->RemoveAt(i);

which looks like it shifts the entire array of elements by one to make root for 
the insert, and then shifts back the entire array of elements by one to 
accomodate the removal.

This needs to go away, and use a std library implementation, which might 
actually be quick.

Original issue reported on code.google.com by tsepez@chromium.org on 5 Nov 2014 at 11:47