Python Program to Implement Intro sort

Intro sort is a sorting algorithm that combines the strengths of three different sorting algorithms: quicksort, heapsort, and insertion sort. It is designed to provide efficient sorting performance in various scenarios while avoiding the worst-case behavior of quicksort. Intro sort starts with quicksort, but if the recursion depth becomes too large, it switches to heapsort to ensure a worst-case time complexity of O(n log n).

Problem Statement

You are required to implement the Intro sort sorting algorithm in python. Intro sort is a hybrid sorting algorithm that combines the strengths of quicksort, heapsort, and insertion sort to achieve efficient sorting performance in various scenarios.

Python Program to Implement Intro sort

import math

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

def insertion_sort(arr, low, high):
    for i in range(low + 1, high + 1):
        key = arr[i]
        j = i - 1
        while j >= low and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

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

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def introsort(arr, depth_limit=None):
    if depth_limit is None:
        depth_limit = 2 * math.log(len(arr))
    if len(arr) <= 1:
        return
    
    if depth_limit == 0:
        heapsort(arr)
        return
    
    pivot = partition(arr, 0, len(arr) - 1)
    introsort(arr[:pivot], depth_limit - 1)
    introsort(arr[pivot + 1:], depth_limit - 1)

def sort(arr):
    introsort(arr)
    insertion_sort(arr, 0, len(arr) - 1)

# Example usage
arr = [3, 9, 1, 7, 5, 4]
print("Original array:", arr)
sort(arr)
print("Sorted array:", arr)

How it Works

1. Initial Setup:
   • The algorithm takes an array of elements as input that needs to be sorted.
2. Quicksort Phase:
   • Introsort starts with a quicksort phase. It chooses a pivot element from the array. Common choices include the first, last, or median element.
   • The array is partitioned into two subarrays: elements less than or equal to the pivot, and elements greater than the pivot.
   • Quicksort is recursively applied to both subarrays.
3. Recursion Depth Check:
   • During the quicksort phase, introsort checks the recursion depth.
   • If the recursion depth becomes too large (exceeds a predetermined limit), the algorithm switches to the heapsort phase to avoid potential worst-case time complexity of quicksort.
4. Heapsort Phase:
   • If the recursion depth limit is exceeded, introsort switches to heapsort.
   • In the heapsort phase, the array is transformed into a max-heap structure. This is done by treating the array as a binary heap and applying a heapify operation.
   • The largest element (root of the max-heap) is swapped with the last element in the array.
   • The heap size is reduced by one, and the heapify operation is applied to maintain the max-heap property.
   • This process is repeated until the entire array is sorted.
5. Insertion Sort:
   • For small subarrays, introsort may switch to insertion sort instead of quicksort.
   • Insertion sort is efficient for small arrays because it has a low overhead and works well when the number of elements is small.
   • Introsort might choose to use insertion sort when the size of the subarray becomes very small.
6. Final Sorted Array:
   • After the heapsort phase or insertion sort, the entire array is sorted.

The key idea behind Introsort is to use quicksort for its efficiency in most cases, but to fall back to heapsort when quicksort’s worst-case behavior might be encountered due to factors like poor pivot selection. By combining these three sorting strategies, Introsort aims to provide good average-case performance while avoiding worst-case scenarios.

It’s important to note that the exact implementation and parameters of Introsort can vary, and some programming languages or libraries might have different optimizations and approaches to achieve the desired performance characteristics.

Input/ Output