Intro Sort

In this article, we will discuss about the Introspective or Intro sort algorithm which is an efficient Hybrid Sorting Algorithm making use of Quick Sort, Heap Sort and Insertion Sort.

What we will see:-

• Introspective Sort Algorithm
  • Quick sort
  • Heap sort
  • Insertion sort
  • Code for Intro sort
• Analysing the Time Complexity for
  • Worst Case
  • Average Case
  • Best Case
• Analysing the Space Complexity
• Conclusion
• References

Pre-requisites:

• Quick Sort
• Heap Sort
• Insertion Sort

Introspective Sort

Intro or Introspective sort is a hybrid sorting algorithm that provide fast performance. It is a comparison based sorting algorithm based on three phases. It uses the quicksort sort along with heapsort and insertion-sort algorithms.

Quick Sort
Quick sort is a divide and conquer algorithm which works by selecting a pivot element in the array, then partitions the other elements into two subarrays checking the condition whether the elements are greater or smaller. On average the quick sort alogirthm takes O(nlog(n)) time, with worst case complexity of O(n²).

Heap Sort
Heap sort algoirthm is a binary-heap based comparison based sorting method. It is an unstable sorting algorithm with worst case and average case time complexity of O(nlog(n)), and best case time complexity of O(n).

Insertion Sort
Insertion sort algorithm is a simple sorting method that builds the final sorted array one item at a time. It's time complexity for worst case and average case is O(n²) and best case is O(n).

Introsort algorithm combines the good parts of these three algorithms. It begins with quick sort, switching to heapsort when the recursion depth exceeds a level based on the number of elements begin sorted and switchs to insertion sort when the number of elements are less than some threshold value.

• If the partition size is such that there is a possibility to exceed the maximum depth limit then the Introsort switches to Heapsort.
• If the partition size is too small then Quicksort switches to Insertion Sort.
• If the partition size is under the limit and not too small, then it performs a simple quicksort.

Code for Intro sort

The introsort algorithm is simillar to quick sort algorithm in terms of implementation and underlying idea, with a key modification. The key modification to quicksort to avoid quadratic worst-case behavior is to make the algorithm aware of how many subproblem levels it is generating. It can then avoid the performance problem by switching to heapsort when the number of levels reaches a limit. Although any choice for the constant factor in this bound will ensure an overall time bound of O(nlog(n)), it must not be so small that the algorithm calls heapsort too frequently. In the following pseudo-code, the depth limit is 2*floor(log₂(n)).

Pseudo-code for Intro-sort

INTROSORT(A, f, b)
    Inputs:-
        A : data structure containing data in positions A[f], ..., A[b-1]
        f : the first position of the sequence
        b : the first position beyond the end of the sequence
    maximum_depth ← 2*floor(log(b-f))
    INTROSORT_LOOP(A, f, b, maximum_depth)
    INSERTION_SORT(A, f, b)
    
INTROSORT_LOOP(A, f, b, depth_limit : a non-negative integer)
    while b-f > size_threshold
    
        // SWITCHING TO HEAPSORT IF DEPTH LIMIT IS 0
        do if depth_limit = 0
            return HEAPSORT(A, f, b)
        
        // DECREMENTING THE DEPTH LIMIT
        depth_limit ← depth_limit - 1
        
        // PARTITIONING AROUND THE PIVOT POINT
        p ← PARTITION(A, f, b, MEDIAN_OF_3(A[f], A[f+(b-f)/2], A[b-1]))
        
        // PERFORMING INTROSORT_LOOP ON ELEMENTS AFTER THE PIVOT VALUE
        INTROSORT_LOOP(A, p, b, depth_limit)
        
        b ← p

The MEDIAN_OF_3 function evaluate the median of first, middle and the last element of the data structure.
PARTITION function finds the pivot element in a given data structure.
In INTROSORT_LOOP, it is possible to omit the test for recursing on the smaller half of the partition, since the depth limit puts an O(log(n)) bound on the stack depth anyway. This omission nicely offsets the added test for exceeding the depth-limit, keeping the algorithm's overhead essentially the same as QUICKSORT's.

Python Implementation of Intro Sort

def introsort(arr):
    # Max depth = 2 * (floor(log2(len(arr))))
    maxdepth = (len(arr).bit_length() - 1)*2
    introsort_helper(arr, 0, len(arr), maxdepth)

def introsort_helper(arr, start, end, maxdepth):
    if end - start <= 1:
        return
    elif maxdepth == 0:
        heapsort(arr, start, end)
    else:
        p = partition(arr, start, end)
        introsort_helper(arr, start, p+1, maxdepth - 1)
        introsort_helper(arr, p+1, end, maxdepth - 1)

def partition(arr, start, end):
    pivot = arr[start]
    i = start - 1
    j = end

    while True:
        i += 1
        while arr[i] < pivot:
            i += 1
        
        j -= 1
        while arr[j] > pivot:
            j -= 1
        
        if i >= j:
            return j

        swap(arr, i, j)

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

def heapsort(arr, start, end):
    build_max_heap(arr, start, end)
    for i in range(end - 1, start, -1):
        swap(arr, start, i)
        max_heapify(arr, index=0, start=start, end=i)

def build_max_heap(arr, start, end):
    def parent(i):
        return (i-1)//2
    length = end - start
    index = parent(length - 1)
    while index >= 0:
        max_heapify(arr, index, start, end)
        index -= 1

def max_heapify(arr, 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 arr[start + l] > arr[start + index]):
        largest = l
    else:
        largest = index
    if (r < size and arr[start + r] > arr[start + largest]):
        largest = r
    if largest != index:
        swap(arr, start+largest, start+index)
        max_heapify(arr, largest, start, end)

arr = [int(i) for i in input().split()]
introsort(arr)
print(arr)

Analysing the Time Complexity

In the quick sort phase of the algorithm, the pivot can either be chosen using the first or last element of the array or by using median-of-3 concept. The simplest pivot selection algorithm is to take the first or the last element of the array as the pivot. The median-of-3 pivot selection algorithm takes the median of the first, middle and last elements of the array. For the data with large number of elements, the median-of-3 approach slows down the running time of the algorithm.

Worst Case
The O(log(n)) subproblem tree depth limit and an O(nlog(n)) worst-case time bound for HEAPSORT, the worst-case computing time for INTROSORT is O(nlog(n)), improving the worst case time complexity of quick sort with O(n²).

Average Case
The average case time complexity of intro sort is O(nlog(n)).

Best Case
The best case time complexity of intro sort is O(nlog(n)).

Space Complexity

The auxiliary space required by the introsort algorithm is O(n) for the call stack when the naive quicksort algorithm is used. To keep the stack depth bounded by O(log(n)), recur first into the partition's smaller side, then use a tail call to recur into the other. Thus, the space complexity of introsort algorithm is O(log(n)).

Conclusion

Introsort is an hybrid algorithm which combines the quicksort, heapsort and insertion sort algorithms. It's main function is switch to another algorithm where the current sort method takes more time. It performs better than quicksort in worst-case configuration. The time complexity of introsort in worst and average case is O(nlog(n)) with use of O(log(n)) auxillary recursion stack space. The Introsort or Introspective sort is used in the sort function of C++ STL. There are many other hybrid sorting algorithms, such as Tim sort which uses two sorting algorithms of insertion sort and merge sort used in the sort function of Jave and Python, Advanced Quick sort which is a hybrid of quick-sort, insertion sort, and selection sort.