4 ms·
Nearly All Binary Searches and Mergesorts are Broken (2006)
- ggchappell 13y agoI remember when this came out. I looked at the code for Binary Search & Merge Sort that I had written for a Data Structures and Algorithms class I was teaching at the time. Neither of these had the bug. The reason was that I was using C++ iterators. template<typename RAIter> void mergeSort(RAIter first, RAiter last); So I could not do RAIter middle = (first + last) / 2; because the there is no operator+ on iterators in general. Instead, I did size_t size = last - first; RAIter middle = first + size/2; and that is correct. The efficiency concerns in the article are a little pointless, at least in the context of my code, since I needed to compute the size anyway. // BASE CASE if (size <= 1) return; I'm not exactly sure what the lesson is here. Although certainly types with restrictions on the operations available can be a Good Thing.
- dang 13y agoSince this had a significant discussion less than a year ago (https://news.ycombinator.com/item?id=6799336 https://news.ycombinator.com/item?id=6799336), we're going to bury this as a dupe. Please check HN Search for the title of a story before posting. It doesn't work for everything, but it found this one.