Heapsort algorithm performs poorly compared to another

Question

I have two heapsort algorithms. The first one was written by me, and the second one from some website. For me, both have the same logic, but the second does better than the first. Why is this happening? The only difference that I see is that mine uses recursion and the other is iterative. Could this be a differentiating factor?

My code is:

 def heapify(arr,i,n): pivot = arr[i] #the value of the root node left,right = (i<<1)+1,(i<<1)+2 #indices of the left and right subtree root nodes if right <= n-1: #if right is within the array, so is left if arr[left] <= pivot and arr[right] <= pivot: return #if both are less than the root node, it already heapified maximum = left if arr[left] >= arr[right] else right #else find which child has a higher value arr[maximum],arr[i] = arr[i],arr[maximum] #swap the root node with that child return heapify(arr,maximum,n) #make the changed child the new root and recurse else: if left <= n-1: #right is outside the array, so check for left only if arr[left] <= pivot: return arr[i],arr[left] = arr[left], arr[i] #same logic as above return heapify(arr,left,n) else: return def heapit(array,n): for i in range((len(array)-1)/2,-1,-1): #all elements after (len(array)-1)/2 are the leaf nodes, so we have to heapify earlier nodes heapify(array,i,n) def heapsort(array): n = len(array) for i in range(n,0,-1): heapit(array,i) #make the array a heap array[0],array[i-1] = array[i-1],array[0] #swap the root node with the last element 

Another code:

 def HeapSort(A): def heapify(A): start = (len(A) - 2) / 2 while start >= 0: siftDown(A, start, len(A) - 1) start -= 1 def siftDown(A, start, end): root = start while root * 2 + 1 <= end: child = root * 2 + 1 if child + 1 <= end and A[child] < A[child + 1]: child += 1 if child <= end and A[root] < A[child]: A[root], A[child] = A[child], A[root] root = child else: return heapify(A) end = len(A) - 1 while end > 0: A[end], A[0] = A[0], A[end] siftDown(A, 0, end - 1) end -= 1 

Even for a small array about 100,000 in size, the difference becomes significant. I call any code simply by passing an array to sort into a function: HeapSort(list) or HeapSort(list) .

Edit:

I replaced the heapsort function with this:

 def heapsort(array): n = len(array) heapit(array,n) array[n-1],array[0] = array[0],array[n-1] for i in range(n-1): heapify(array,0,n-1-i) array[ni-2],array[0] = array[0],array[ni-2] 

This gives comparable performance, but still slower. For an array of $ 1 million, the result is almost 20 seconds: 4 seconds. What else can be done?

Answer 1

EDIT : my comments below may explain the serious slowdown, but most importantly, your algorithm is not a heapsort.

Inside the heapsort function, a for i in range(n,0,-1) heapsort is executed. This is n iterations, where n is the size of your input. Inside this loop, you call heapit , which loops for i in range((len(array)-1)/2,-1,-1) ; which is approximately n//2 iterations.

n * (n // 2) = Θ ( n ²). In other words, you have an algorithm that takes at least quadratic time, while the second algorithm implements a true heapsort that works in O ( n lg n ).

/ EDIT

Most likely, recursion, which kills performance, is combined with calling functions defined at the module level. Python (at least CPython) is not optimized for recursive programs, but for iterative ones. For each recursive call in heapify CPython must execute the following instructions with code of seven bytes:

  9 158 LOAD_GLOBAL 0 (heapify) 161 LOAD_FAST 0 (arr) 164 LOAD_FAST 6 (maximum) 167 LOAD_FAST 2 (n) 170 CALL_FUNCTION 3 173 RETURN_VALUE >> 174 POP_TOP 

(determined using dis ). The last two instructions are executed after the recursive call is completed, because Python does not perform tail call optimization . p>

Although this may seem LOAD_GLOBAL , LOAD_GLOBAL must have at least one hash lookup to find heapify and reference counts for heapify , arr , maximum and i should be increased. When the recursive call ends, reference counts should be reduced again. Function calls are quite expensive in Python.

As import this says, "flat is better than nested": if possible, prefer iteration over recursion.