Intro Sort Algorithm
IntroSort (Introspective Sort) is a hybrid sorting algorithm that combines the quickness of Quick Sort with the robustness of Heap Sort and Insertion Sort. It was invented by David Musser in 1997 and is designed to provide optimal performance for various types of input data by adapting to the data’s characteristics.
How IntroSort Works:
- Initial Phase (Quick Sort):
- IntroSort begins by performing Quick Sort, which is efficient for most datasets. Quick Sort is a divide-and-conquer algorithm that selects a pivot element and partitions the array around the pivot. Elements less than the pivot are moved to the left of the pivot, and elements greater than the pivot are moved to the right.
- Switch to Heap Sort:
- To avoid the worst-case performance of Quick Sort (O(n²)), IntroSort monitors the recursion depth. If the recursion depth exceeds a certain level, which is typically logarithmic in relation to the number of elements (2 * log2(n)), the algorithm switches to Heap Sort. Heap Sort has a guaranteed worst-case time complexity of O(n log n).
- Final Phase (Insertion Sort):
- When the partitions become small (usually below a certain threshold, like 16 elements), IntroSort switches to Insertion Sort. Insertion Sort is efficient for small datasets and nearly sorted arrays due to its low overhead.
Characteristics of IntroSort:
- Time Complexity:
- Best Case: O(n log n) – Quick Sort is used, and the partitions are balanced.
- Average Case: O(n log n) – Typical behavior, combining Quick Sort and Heap Sort.
- Worst Case: O(n log n) – Heap Sort prevents the worst-case O(n²) behavior of Quick Sort.
- IntroSort provides optimal performance by combining the strengths of its component algorithms.
- Space Complexity:
- IntroSort uses additional space for the recursion stack during Quick Sort, but this is generally limited to O(log n) space.
- Stability:
- IntroSort is not a stable sort because Heap Sort and Quick Sort are not stable. Stability refers to preserving the relative order of records with equal keys.
- Usage:
- IntroSort is suitable for a wide range of applications due to its adaptability and optimal performance. It is used in standard libraries of many programming languages, including C++ (as part of the STL sort function).
Code Example
import math
def insertion_sort(arr, left, right):
for i in range(left + 1, right + 1):
key = arr[i]
j = i - 1
while j >= left and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[i] < arr[left]:
largest = left
if right < n and arr[largest] < arr[right]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heap_sort(arr, left, right):
n = right - left + 1
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
heapify(arr, i, 0)
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 introsort_util(arr, low, high, maxdepth):
if high - low <= 16:
insertion_sort(arr, low, high)
elif maxdepth == 0:
heap_sort(arr, low, high)
else:
pivot = partition(arr, low, high)
introsort_util(arr, low, pivot - 1, maxdepth - 1)
introsort_util(arr, pivot + 1, high, maxdepth - 1)
def introsort(arr):
maxdepth = int(math.log2(len(arr))) * 2
introsort_util(arr, 0, len(arr) - 1, maxdepth)
return arr
# Example usage
arr = [12, 11, 13, 5, 6, 7]
sorted_arr = introsort(arr)
print("Sorted array is:", sorted_arr)Code Explanation
Insertion Sort Function
def insertion_sort(arr, left, right):
for i in range(left + 1, right + 1):
key = arr[i]
j = i - 1
while j >= left and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key- This function performs an insertion sort on the subarray from
lefttoright.
Heapify Function
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[i] < arr[left]:
largest = left
if right < n and arr[largest] < arr[right]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)- This function ensures the subarray rooted at index
isatisfies the heap property.
Heap Sort Function
def heap_sort(arr, left, right):
n = right - left + 1
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
heapify(arr, i, 0)- This function sorts the subarray from
lefttorightusing heap sort.
Partition Function
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- This function partitions the array around the pivot and returns the pivot index.
IntroSort Utility Function
def introsort_util(arr, low, high, maxdepth):
if high - low <= 16:
insertion_sort(arr, low, high)
elif maxdepth == 0:
heap_sort(arr, low, high)
else:
pivot = partition(arr, low, high)
introsort_util(arr, low, pivot - 1, maxdepth - 1)
introsort_util(arr, pivot + 1, high, maxdepth - 1)- This function performs the actual introspective sort. It switches between insertion sort, heap sort, and quick sort based on the size of the subarray and recursion depth.
IntroSort Function
def introsort(arr):
maxdepth = int(math.log2(len(arr))) * 2
introsort_util(arr, 0, len(arr) - 1, maxdepth)
return arr- This function initializes the maximum depth for recursion and calls the
introsort_utilfunction.
Example Usage
arr = [12, 11, 13, 5, 6, 7]
sorted_arr = introsort(arr)
print("Sorted array is:", sorted_arr)- An example list
arris sorted using theintrosortfunction, and the sorted list is printed.
Output
Sorted array is: [5, 6, 7, 11, 12, 13]- The final output is the sorted array in ascending order.
