Introspective Sort

Introspective Sort

·

4 min read

Introspective sort(introsort) is a hybrid sorting algorithm. It tries to achieve better result by combining quick sort, heap sort and selection sort. In this article, let's see how it works.

Because introspective sort uses those 3 algorithms, so let's implement them first.

Let's begin from the most simple one: selection sort. The idea is very simple, for every element, compare it with elements before it, move elements to the right until current element is bigger.

function insertionSort(nums: number[], left: number, right: number): void {
    for (let i = left + 1; i <= right; i++) {
        // current element as key
        const key = nums[i];

        // iterate from i-1 to left
        // if nums[j] > key, then move nums[j] to the right
        let j = i - 1;
        for (; j >= left && nums[j] > key; j--) {
            nums[j + 1] = nums[j];
        }

        // insert key into appropriate place
        nums[j + 1] = key;
    }
}

Next is heap sort. I wrote an article about heap sort before, so I will not repeat here. Check that article first if you are not familiar with it. Here is the code of heap sort.

type HeapqComparator<T> = (t1: T, t2: T) => boolean;

class heapq {

    public static heapify<T>(elements: T[], comparator: HeapqComparator<T>) {
        for (let i = elements.length - 1; i >= 0; i--) {
            heapq._heapify(elements, i, comparator);
        }
    }

    private static _heapify<T>(elements: T[], index: number, comparator: HeapqComparator<T>) {
        const lci = index * 2 + 1;
        const rci = index * 2 + 2;

        let topi = index;

        // note the arguments order the function comparator
        // if its in heap, then we need elements[topi] - elements[lci] > 0
        if (lci < elements.length && comparator(elements[topi], elements[lci])) {
            topi = lci;
        }
        if (rci < elements.length && comparator(elements[topi], elements[rci])) {
            topi = rci;
        }

        if (topi !== index) {
            [elements[topi], elements[index]] = [elements[index], elements[topi]];
            heapq._heapify(elements, topi, comparator);
        }
    }

    public static heappush<T>(elements: T[], val: T, comparator: HeapqComparator<T>) {
        elements.push(val);
        heapq._swapWithParent(elements, elements.length - 1, comparator);

    }

    private static _swapWithParent<T>(elements: T[], index: number, comparator: HeapqComparator<T>) {
        if (index === 0) return;
        const pi = Math.trunc((index - 1) / 2);

        // note the arguments order the function comparator
        // if its min heap, then we need elements[pi] - elements[index] > 0
        if (comparator(elements[pi], elements[index])) {
            [elements[index], elements[pi]] = [elements[pi], elements[index]];
            heapq._swapWithParent(elements, pi, comparator);
        }
    }

    public static heappop<T>(elements: T[], comparator: HeapqComparator<T>): T {
        const res = elements[0];
        elements[0] = elements[elements.length - 1];
        elements.splice(elements.length - 1, 1);
        heapq._heapify(elements, 0, comparator);
        return res;
    }
}

function heapSort(nums: number[]) {
    const comparator = (a: number, b: number) => (a - b) > 0;
    const heapNums = [...nums];
    heapq.heapify(heapNums, comparator);
    for (let i = 0; i < nums.length; i++) {
        nums[i] = heapq.heappop(heapNums, comparator);
    }
}

OK, now let's see how introsort combines quick sort with heap sort and selection sort.

Introsort use quick sort as a base sort algorithm. When some conditions are met, then switch to other algorithms.

The first condition is, for every iteration from the quick sort, if current array's length is lower then 16, then use quick sort. This decision is because, even if the time complexity of selection sort is O(n^2), for small array, selection sort usually runs faster.

The second condition is, introsort defined a max depth value according to the length of the array. We know that if we can't choose the right pivot in quick sort, then the time complexity can becomes O(n^2). So to prevent this case, when the process of quick sort run out of the depth limit, then we just give up quick sort, and switch to heap sort.

Yes, that's all the details. Let's implement it in code.

function partition(nums: number[], low: number, high: number): number {
    let pivot = nums[high];
    let p = low;
    for (let i = low; i < high; i++) {
        if (nums[i] <= pivot) {
            [nums[i], nums[p]] = [nums[p], nums[i]];
            p += 1;
        }
    }
    [nums[high], nums[p]] = [nums[p], nums[high]];
    return p;
}

function _introSort(nums: number[], left: number, right: number, depthLimit: number) {
    if (left > right) return;

    if (right - left < 16) {
        // size is lower then 16, use insertion sort
        insertionSort(nums, left, right);

    } else {
        if (depthLimit <= 0) {
            // run out of depth limit, switch to heap sort
            heapSort(nums);

        } else {
            // run normal quick sort process
            const mid = partition(nums, left, right);
            _introSort(nums, left, mid - 1, depthLimit - 1);
            _introSort(nums, mid + 1, right, depthLimit - 1);
        }
    }
}

function introSort(nums: number[]) {
    const left = 0;
    const right = nums.length - 1;

    // predefined the depth limit
    const depthLimit = 2 * Math.floor(Math.log2(nums.length));
    _introSort(nums, left, right, depthLimit);
}