# Why does this mergesort variant not do Θ(n) comparisons on average?

A comparison sort cannot require fewer than $\Theta (n\log n)$ comparisons on average. However, consider this sorting algorithm:

sort(array):
if length(array) < 2:
return array
unsorted ← empty_array
i ← 0
while i < length(array) - 1:
if array[i] > array[i + 1]:
push(unsorted, pop(array, i + 1))
else:
i ← i + 1
return merge(array, sort(unsorted))


(push(array, element) puts the new element at the end of the array and increases the array’s length by 1. pop(array, index) removes the element at that index from the array, moving all the elements at greater indices and decrementing the array’s length, and returns the removed element. merge is the same as in mergesort.)

Instead of simply splitting the array in the middle like mergesort, it splits it so that one resulting array doesn’t need to be recursively sorted. Let $n$ be the length of the array to be sorted. Applying the Master Theorem gives us

\begin{align*} T(n) &= T(n / b) + \mathrm{splitComparisons}(n) + \mathrm{mergeComparisons}(n) \\ &= T(n / b) + (n - 1) + n \\ &= T(n / b) + 2n - 1\,, \end{align*}

so $f(n) = 2n - 1$ and $a = c = 1$ in the statement of the Master Theorem.

$b$ is one over the probability that an element is greater than the next element and will go into the array to be recursively sorted. For example, if there's a 25% chance that array[i] > array[i + 1] (for all i), $b = 4$. $b$ is clearly greater than $1$, since the length of unsorted array grows smaller with every recursive call, so taking the logarithm with base $b$ of $1$ will always give us $0$, which is less than $c$. Then $T(n) = \Theta(f(n)) = \Theta(n)$.

But that can’t be true, so the Master Theorem isn't applicable for some reason; I suspect because $b$ isn't constant, but I don’t know how to prove that. The worst case of the sorting algorithm obviously requires a quadratic number of comparisons and the best case linear, so by analogy with bubblesort, insertion sort, etc, I’m guessing this algorithm also makes a quadratic number of comparisons on average.

• You need to define exactly what you mean by $T(n) = T(n/b) + \dots$. Where is that coming from? What's this $b$ that's suddenly appeared? You can't just write down formulas without relating them to what they're supposed to be describing. I suspect that, if you try to state exactly what that formula means, it will become clear that it doesn't actually represent the behaviour of the algorithm. – David Richerby Apr 9 '15 at 16:35
• b is one over the probability that an element is greater than the next element and will go into the array to be recursively sorted. For example, if there's a 25% chance that array[i] > array[i + 1] (for all i), b = 4. Intuitively, it seems equally likely that an element of an array would be greater than or less than the previous element, so b = 2. However, the problem remains even if b isn't 2, as long as it is constant and greater than 1. That's why I think b depends on i (and therefore also on n). – Mets Apr 9 '15 at 16:53
• @David Richerby Another way to think about it is that mergesort forms a tree with height log(n), where each node is a single recursive call, but this algorithm only contains the rightmost (leftmost) calls on each level of the tree. Looking at the rightmost calls, we get a geometric series: n + (n / b) + (n / b^2) + ..., which sums to a constant times n. – Mets Apr 9 '15 at 17:08
• @RickyDemer As I understood from reading that article, the Master Theorem is for solving recurrence relations of a certain form. Whether they represent the average or worst or best case running time isn't important. If I'm mistaken, I could state the question without it. It just seemed like a simple way to present the question. – Mets Apr 9 '15 at 17:16
• If your ansatz leads you to a linear number of comparisons, the ansatz is wrong. In particular, I suspect there is no such $b$ (so that the expected size of unsorted is $n/b$). – Raphael Apr 9 '15 at 20:08

Since you don't do any reordering while splitting, the length of array after the while loop can not be larger than the length of the longest increasing subsequence in the input. Since that one is on average about $2\sqrt{n}$ elements long¹, you keep too many elements in unsorted.

In particular, there is no $b$ so that your ansatz describes the actual number of comparisions.

Assuming that the probability distribution of the length of the longest increasing subsequence survives your splitting, a proper ansatz would be of the form

$\qquad\displaystyle C(n) = C(n - 2\sqrt{n}) + \Theta(n)$

which does not seem to solve² to $C \in O(n)$.

In fact, it's even worse since you keep the "first" increasing subsequence, not the longest (in general); consider for instance $[1,n,2,3,4,\dots,n-1]$; you keep $[1,n]$ and recurse on $[2,3,\dots,n-1]$.

1. On the distribution of the length of the longest increasing subsequence of random permutations by J. Baik, P. Deift and K. Johansson (1999) [via Wikipedia]
2. I have not solved it explicitly, but plots suggest as much.
• So the problem was indeed that $b$ isn't constant. Thank you. – Mets Apr 9 '15 at 20:50

You seem to be assuming that pop takes $O(1)$ time. That assumption is wrong.

You can't implement pop in $O(1)$ time, since pop requires shifting all elements after index one to the left, which is $O(n)$ time using the obvious implementation. (There are modestly better methods, but nothing that achieves $O(1)$ time like you are implicitly assuming. If you want to claim a particular running time, it's your job to specify how you plan to implement push and pop and justify their running time carefully.)

Consequently, the time complexity of your algorithm is not $O(n)$.

• pop is O(n) in the number of assignments, which I don't care about. However, pop is O(1) in the number of comparisons, which is what I'm interested in. – Mets Apr 9 '15 at 16:10
• @Mets, I don't understand your comment. Your question asks why the time complexity isn't $O(n)$; my answer explains why the time complexity isn't $O(n)$. You say you already knew that the number of assignments isn't $O(n)$; if so, that already tells you that the time complexity isn't $O(n)$. So what's your question? (If your question is about the number of comparisons not the time complexity, you need to edit the question, as nowhere in the question do you say that -- the question refers repeatedly to time complexity.) – D.W. Apr 9 '15 at 16:13
• I'll make it more explicit that I only care about comparisons. Sorry for making the answer incorrect. – Mets Apr 9 '15 at 16:14
• @Mets, OK, sounds good. A tip for the future: please make sure the question is crafted to ask what you want to know. People on StackExchange sites sometimes don't like questions that change to ask something different after receiving an answer to the question you asked – D.W. Apr 9 '15 at 16:17
• @Mets Bear in mind that "time complexity" has a well-defined meaning: it refers to the number of steps required. I've edited the question so that your "time complexity in terms of comparisons" is just "number of comparisons". – David Richerby Apr 9 '15 at 16:25

Assuming input array is in decreasing order, then array[i] > array[i+1] is always satisfied, your algorithm would move all but the first item from array to unsorted. The running time is at least $\Omega(n^2)$.

Let array array' denote the same variable before and after the while loop. Then array[i] is left in array' if and only array[i] is (one of) the biggest among array, ..., array[i]. In expectation, there would be only $O(\log n)$ items left in array', assuming the input array is random.

• Even if "input array is in decreasing order," his algorithm would initialize $i$ to zero and never decrease $i$ and only ever move entries with index larger than $i$ from array to unsorted. $\:$ In particular, array will never be moved from array to unsorted. $\:$ Do you have an example for which array won't be sorted after the while loop? $\;\;\;\;$ – user12859 Apr 9 '15 at 18:05
• I have implementations of this algorithm in Lua and C and have tested this case. – Mets Apr 9 '15 at 18:25
• I've not checked if the algorithm's correct but your counterexample is incorrect, as @RickyDemer points out. – David Richerby Apr 9 '15 at 18:47
• Thank you @RickyDemer and DavidRicherby, I should have missed a +1 somewhere. – Tianren Liu Apr 9 '15 at 20:16
• Decreasing order is the worst case, but I'm interested in the average case. – Mets Apr 9 '15 at 20:21