Intro Sort: A brief introduction

Intro sort

Intro or introspective sort is a sorting weapon used by the STL library in C++ and array sorting in the swift programming language. In simple terms, it is currently, the best sorting algorithm. In this article, we dive into the details of the intro sort algorithm and analyze why it is regarded as the best sorting algorithm.

Intro sort is a hybrid comparison-based sorting algorithm that consists of three sorting phases. These three sorting phases or algorithms minimize the run time. The three sorting algorithms used in intro sort are Quicksort, Insertion sort, Heapsort.

Note: Introsort is not stable.

This means that two objects with equal values may or may not appear in the same order in sorted output as they appear in the input unsorted array

Why do we need Intro sort?

Quicksort

Quicksort is one of the efficient algorithms based on the divide and conquer method. It has a complexity of NlogN in its best and average case but has O(N²) in its worst time performance. The complexity of Quicksort depends upon the choice of the pivot element and the depth of the recursion tree. It also uses O(N) auxiliary space.

Heapsort

Heapsort always has a time performance of O(NLogN) which is significantly better than the worst time complexity of quicksort O(N²). So, is heapsort the best sorting algorithm? The answer is no. In quicksort, no swapping of elements occurs if the array is sorted whereas, in heapsort, the swapping of elements is unavoidable. The best thing about heapsort is that the time complexity remains O(nlogn) irrespective of the recursion depth.

Mergesort

Mergesort is also a divide and conquer algorithm with a time complexity of O(NlogN). Mergesort can be used irrespective of the size of the data sets. Mergesort works well with LinkedList whereas quicksort is better with arrays. Generally, with memory constraints, quicksort outperforms merge sort.

Insertion sort

Insertion sort is simple and easy to implement. Insertion sort is good for small data sets but the performance deteriorates with the increase in the size of the data list. It has minimal space requirements but has a time performance of O(N²).

Why is mergesort not used?

When to switch from quicksort to heapsort?

Based on the above analysis, the working of intro sort can be summarized as,

  1. Intro sort begins with quicksort and if the recursion depth exceeds the depthlimit of intro sort, switching to heapsort takes place.
  2. If the number of elements is few, insertion sort takes place.

Therefore, the first step is to create a partition. After creating a partition, three cases arise,

  1. If the partition size is greater than the depthlimit i.e 2*logN, switching to heap sort takes place.
  2. If the partition size is too small, switching to insertion sort takes place. The constant below which insertion sort is used is chosen to be 16 based on research. Therefore, if the size of the partition is less than or equal to 16, insertion sort takes place.
  3. If the partition size is greater than 16 and less than the depthlimit (2*logN), quicksort is performed.

FLOWCHART

PSEUDO CODE

depthLimit = 2xfloor(log(length(A)))

introsort(A, depthLimit)

introsort(A, depthLimit):

n = length(A)

if n<=16:

insertionSort(A)

if depthLimit == 0:

heapsort(A)

else:

p = partition(A)

introsort(A[0:p-1], depthLimit — 1)

introsort(A[p+1:n], depthLimit — 1)

Implementation in C++

uses Introsort. */

#include<bits/stdc++.h>

using namespace std;

// A utility function to swap the values pointed by

// the two pointers

void swapValue(int *a, int *b)

{

int *temp = a;

a = b;

b = temp;

return;

}

/* Function to sort an array using insertion sort*/

void InsertionSort(int arr[], int *begin, int *end)

{

int left = begin — arr;

int right = end — arr;

for (int i = left+1; i <= right; i++)

{

int key = arr[i];

int j = i-1;

while (j >= left && arr[j] > key)

{

arr[j+1] = arr[j];

j = j-1;

}

arr[j+1] = key;

}

return;

}

// A function to partition the array and return

// the partition point

int* Partition(int arr[], int low, int high)

{

int pivot = arr[high]; // pivot

int i = (low — 1); // Index of smaller element

for (int j = low; j <= high- 1; j++)

{

if (arr[j] <= pivot)

{

i++;

swap(arr[i], arr[j]);

}

}

swap(arr[i + 1], arr[high]);

return (arr + i + 1);

}

// A function that find the middle of the

// values pointed by the pointers a, b, c

// and return that pointer

int *MedianOfThree(int * a, int * b, int * c)

{

if (*a < *b && *b < *c)

return (b);

if (*a < *c && *c <= *b)

return ©;

if (*b <= *a && *a < *c)

return (a);

if (*b < *c && *c <= *a)

return ©;

if (*c <= *a && *a < *b)

return (a);

if (*c <= *b && *b <= *a)

return (b);

}

// A Utility function to perform intro sort

void IntrosortUtil(int arr[], int * begin,

int * end, int depthLimit)

{

// Count the number of elements

int size = end — begin;

// If partition size is low then do insertion sort

if (size < 16)

{

InsertionSort(arr, begin, end);

return;

}

// If the depth is zero use heapsort

if (depthLimit == 0)

{

make_heap(begin, end+1);

sort_heap(begin, end+1);

return;

}

// Else use a median-of-three concept to

// find a good pivot

int * pivot = MedianOfThree(begin, begin+size/2, end);

// Swap the values pointed by the two pointers

swapValue(pivot, end);

// Perform Quick Sort

int * partitionPoint = Partition(arr, begin-arr, end-arr);

IntrosortUtil(arr, begin, partitionPoint-1, depthLimit — 1);

IntrosortUtil(arr, partitionPoint + 1, end, depthLimit — 1);

return;

}

void Introsort(int arr[], int *begin, int *end)

{

int depthLimit = 2 * log(end-begin);

// Perform a recursive Introsort

IntrosortUtil(arr, begin, end, depthLimit);

return;

}

// A utility function ot print an array of size n

void printArray(int arr[], int n)

{

for (int i=0; i < n; i++)

printf(“%d “, arr[i]);

printf(“\n”);

}

// Driver program to test Introsort

int main()

{

int arr[] = {3, 1, 23, -9, 233, 23, -313, 32, -9};

int n = sizeof(arr) / sizeof(arr[0]);

// Pass the array, the pointer to the first element and

// the pointer to the last element

Introsort(arr, arr, arr+n-1);

printArray(arr, n);

return(0);

}

OUTPUT

313 -9 -9 1 3 23 23 32 233

Time Complexity

Average Case — O(N log N)

Worse Case — O(N log N)

where N = number of elements to be sorted.

Auxiliary Space

Comparison

Comparison between Quicksort, Heapsort, Insertion sort, Introsort

Typing.....

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store