Nearly All Binary Searches and Mergesorts are Broken (2006)

I 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.

Since this had a significant discussion less than a year ago (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.