title: Number of Comparisons in Merge-Sort
body: <p>I was studying the merge-sort subject that I ran into this concept that the number of comparisons in merge-sort (in the worst-case, and according to <a href="http://en.wikipedia.org/wiki/Merge_sort" rel="noreferrer">Wikipedia</a>) equals (n ⌈lg n⌉ - 2<sup>⌈lg n⌉</sup> + 1); in fact it's between (n lg n - n + 1) and (n lg n + n + O(lg n)). The problem is that I cannot figure out what these complexities try to say. I know O(nlogn) is the complexity of merge-sort but the number of comparisons? </p>