Python Program to Implement Introsort

This is a Python program to implement introsort.

Problem Description

The program sorts a list by introsort.

Problem Solution

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.

Program/Source Code

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:
    elif maxdepth == 0:
        heapsort(alist, start, end)
        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
        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]
print('Sorted list: ', end='')
Program Explanation

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.

Runtime Test Cases
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.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

If you find any mistake above, kindly email to [email protected]

Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.