merge insert sort is pretty goodbut is it optimalrecall from section that no sorting algorithm can be faster than ohm( log nto be precisethe information theoretic lower bound for sorting can be proved to be dlog ! that iswe can prove lower bound of exactly dlog ! comparisons merge insert sort gives us number of comparisons equal to this information theoretic lower bound for all values up to at merge insert sort requires comparisons while the information theoretic lower bound is only comparisons howeverfor such small number of elementsit is possible to do an exhaustive study of every possible arrangement of comparisons it turns out that there is in fact no possible arrangement of comparisons that makes the lower bound less than comparisons when thusthe information theoretic lower bound is an underestimate in this casebecause really is the best that can be done call the optimal worst cost for elements (nwe know that ( < (ndlog( ) because we could sort elements and use binary insert for the last one for all and ms( < (ns(mm (mnwhere (mnis the best time to merge two sorted lists for it turns out that we can do better by splitting the list into pieces of size and and then merging thusmerge sort is not quite optimal but it is extremely goodand nearly optimal for smallish numbers of elements further reading much of the material in this book is also covered in many other textbooks on data structures and algorithms the biggest exception is that not many other textbooks cover lower bounds proofs in any significant detailas is done in this those that do focus on the same example problems (search and selectionbecause it tells such tight and compelling story regarding related topicswhile showing off the major techniques for lower bounds proofs two examples of such textbooks are "computer algorithmsby baase and van gelder [bg ]and "compared to what?by gregory rawlins [raw "fundamentals of algorithmicsby brassard and bratley [bb also covers lower bounds proofs exercises consider the so-called "algorithm for algorithmsin section is this really an algorithmreview the definition of an algorithm from section which parts of the definition applyand which do notis the "algorithm for algorithmsa heuristic for finding good algorithmwhy or why not