3 ms·

I'm not sure what I'm supposed to get from this page. Is this an allusion to bubble-sort's O(n^2) worst-case time complexity?

• bradleyjg 11y ago
  "In all seriousness, I just wanted a quick fix to undo the perf regression caused by using std::stable_sort. I filed a bug to fix this: https://bugs.webkit.org/show_bug.cgi?id=150843" https://bugs.webkit.org/show_bug.cgi?id=150843" From that link "Bug 150843 - Consider something better than bubble sort for insertion sets achristiansen suggested falling back on stable sort if we do too many passes. ggaren suggested insertion sort. There's also the possibility that we could make merge sort a lot faster, if we didn't use system malloc as the temp buffer allocator." Apparently a really slow merge sort implementation caused a major performance slowdown. Since bubble sort is always taught as a bad sort it's kind of funny that he is using it to fix a performance regression. Hence the link and upvotes.
  • omginternets 11y ago
    Ah I see [that there are still uncharted depths of nerd-dom ;)] Thanks for the explanation!
  • brobinson 11y ago
    You have an extra " on the end of your link: https://bugs.webkit.org/show_bug.cgi?id=150843 https://bugs.webkit.org/show_bug.cgi?id=150843
  • venning 11y ago
    > Since bubble sort is always taught as a bad sort... I was taught about bubble sort in three different situations. In each one, bubble sort was not taught as a "bad" sort. The instructor always focused on the difference between worst-case performance and best-case performance. It always forced me to learn how much context matters. Bubble sort should not be used as teaching tool for "bad algorithms" but a teaching tool for understanding your data and how much you really know about it.