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

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.