Tweeted twitter.com/#!/StackCompSci/status/586401503042109441 occurred Apr 10 '15 at 5:33 7 edited tags | link edited Apr 9 '15 at 19:58 Raphael♦ 59k2525 gold badges144144 silver badges327327 bronze badges 6 edited tags | link edited Apr 9 '15 at 17:42 Mets 2855 bronze badges 5 added 293 characters in body edited Apr 9 '15 at 17:35 Mets 2855 bronze badges 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. However$$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. 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. However, $$b$$ is clearly greater than $$1$$, 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. 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. 4 added 11 characters in body; edited title edited Apr 9 '15 at 16:57 Mets 2855 bronze badges 3 Formatting and clarification edited Apr 9 '15 at 16:24 David Richerby 74.9k1616 gold badges117117 silver badges208208 bronze badges 2 added 104 characters in body; edited title edited Apr 9 '15 at 16:16 Mets 2855 bronze badges 1 asked Apr 9 '15 at 15:08 Mets 2855 bronze badges