# Why can't we sort an Array in O(n) using Fibonacci Heap?

If we can insert to a Fibonacci Heap in O(1), and increase-key and find-min in the same W.C time complexity, then why can't we sort an array in time complexity O(n)?

Given an array with n elements:

1. Find the maximum of the array (largest key) in O(n).

2. Build a Fibonacci Heap of the elements in O(n), emptying the array in the proccess.

3. Use find-min and add the result to the now empty array.

4. Use increase-key on the element you found in step 3, and increase it by the maximum of the old array + 1 (making it now larger than any element of the old array)

5. Reapet steps 3 and 4, n times. Each time a new element from the old array is added, because all added elements are larger than max+1.

Increase-key is not a $O(1)$ operation on Fibonacci heaps. You're thinking of decrease-key.
Exercise: Why can't increase-key be a $O(1)$ operation on this data structure?
If it was possible, Heapsort would take $\Theta(n)$ time. This is a contradiction to the lower bound of $\Omega(n\lg n)$ when sorting by comparisons.