The heapsort test algorithm for python 

1. def heapify(arr, n, i):
2.    largest = i  # Initialize largest as root
3.    l = 2 * i + 1     # left = 2*i + 1
4.    r = 2 * i + 2     # right = 2*i + 2
5.  
6.    # See if left child of root exists and is greater than root
7.    if l < n and arr[i] < arr[l]:
8.        largest = l
9.  
10.    # See if right child of root exists and is greater than root
11.    if r < n and arr[largest] < arr[r]:
12.        largest = r
13.  
14.    # Change root, if needed
15.    if largest != i:
16.        arr[i], arr[largest] = arr[largest], arr[i]  # swap
17.  
18.        # Heapify the root.
19.        heapify(arr, n, largest)
20.  
21. def heapSort(arr):
22.    n = len(arr)
23.  
24.    # Build a max heap.
25.    for i in range(n // 2 - 1, -1, -1):
26.        heapify(arr, n, i)
27.  
28.    # Extract elements from heap one by one
29.    for i in range(n-1, 0, -1):
30.        arr[i], arr[0] = arr[0], arr[i]  # swap
31.        heapify(arr, i, 0)
32.  
33. # Testing the heap sort algorithm
34. arr = [12, 11, 13, 5, 6, 7]
35. heapSort(arr)
36. print("Sorted array is:", arr)

Please answer:

• Find the best case, worst case, and average case in time and space complexity. Explain.