Python Program to Implement Introsort

This is a Python program to implement introsort.

The program sorts a list by introsort.

1. Create a function introsort that takes a list argument.
2. In the function, an appropriate value for maxdepth is chosen. Here maxdepth is chosen equal to 2 times floor of log base 2 of the length of the list.
3. Call introsort_helper with start=0 and end=len(alist).
4. The function introsort_helper takes a list and three variables, start, end and maxdepth as arguments. The function sorts the list from indexes start to end – 1 inclusive.
5. The function returns if the length of the list to be sorted is not greater than 1.
6. It performs heapsort from indexes start to end – 1 on the list if maxdepth is 0.
7. Otherwise, partition is called on the list and introsort_helper is called on the two halves of the list.
8. The function parititon uses Hoare’s partition scheme to partition the list.
9. Create a function heapsort that takes a list as argument and variables start and end which specify the indexes across which the sort should be performed.
10. Call build_max_heap to rearrange the list into a list representation of a heap.
11. Swap the first element with the last element in the heap.
12. Consider the new heap to have size one less than its previous size and call max_heapify with index = 0 to make this new heap satisfy the heap property.
13. Repeat steps 11 and 12 until the size of the heap reduces to zero and the entire list is sorted (i.e. from indexes start to end – 1 inclusive).
14. Define the function build_max_heap that rearranges a list specified between indexes start to end – 1 inclusive to form a max heap.
15. The build_max_heap function works by calling max_heapify on each parent node starting from the last parent node and working towards the root.
16. Define the function max_heapify that takes an index as argument and modifies the heap structure at and below the node at this index to make it satisfy the heap property.

Here is the source code of a Python program to implement introsort. The program output is shown below.

def introsort(alist):
    maxdepth = (len(alist).bit_length() - 1)*2
    introsort_helper(alist, 0, len(alist), maxdepth)
 
def introsort_helper(alist, start, end, maxdepth):
    if end - start <= 1:
        return
    elif maxdepth == 0:
        heapsort(alist, start, end)
    else:
        p = partition(alist, start, end)
        introsort_helper(alist, start, p + 1, maxdepth - 1)
        introsort_helper(alist, p + 1, end, maxdepth - 1)
 
def partition(alist, start, end):
    pivot = alist[start]
    i = start - 1
    j = end
 
    while True:
        i = i + 1
        while alist[i] < pivot:
            i = i + 1
        j = j - 1
        while alist[j] > pivot:
            j = j - 1
 
        if i >= j:
            return j
 
        swap(alist, i, j)
 
def swap(alist, i, j):
    alist[i], alist[j] = alist[j], alist[i]
 
def heapsort(alist, start, end):
    build_max_heap(alist, start, end)
    for i in range(end - 1, start, -1):
        swap(alist, start, i)
        max_heapify(alist, index=0, start=start, end=i)
 
def build_max_heap(alist, start, end):
    def parent(i):
        return (i - 1)//2
    length = end - start
    index = parent(length - 1)
    while index >= 0:
        max_heapify(alist, index, start, end)
        index = index - 1
 
def max_heapify(alist, index, start, end):
    def left(i):
        return 2*i + 1
    def right(i):
        return 2*i + 2
 
    size = end - start
    l = left(index)
    r = right(index)
    if (l < size and alist[start + l] > alist[start + index]):
        largest = l
    else:
        largest = index
    if (r < size and alist[start + r] > alist[start + largest]):
        largest = r
    if largest != index:
        swap(alist, start + largest, start + index)
        max_heapify(alist, largest, start, end)
 
 
alist = input('Enter the list of numbers: ').split()
alist = [int(x) for x in alist]
introsort(alist)
print('Sorted list: ', end='')
print(alist)

1. The user is prompted to enter a list of numbers.
2. The list is passed to the introsort function.
3. The sorted list is displayed.

Case 1:
Enter the list of numbers: 3 5 2 3 10 9 3 7 2 1 0 9
Sorted list: [0, 1, 2, 2, 3, 3, 3, 5, 7, 9, 9, 10]
 
Case 2:
Enter the list of numbers: 5 4 3 2 1
Sorted list: [1, 2, 3, 4, 5]
 
Case 3:
Enter the list of numbers: 5
Sorted list: [5]

Sanfoundry Global Education & Learning Series – Python Programs.

To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.