Skip to main content

Introsort

Introsort is a hybrid sorting algorithm that combines two different sorting algorithms to achieve a fast and efficient sorting process. It starts with quicksort, which is a well-known sorting algorithm, and switches to heapsort when the recursion depth exceeds a certain threshold. This threshold is determined by the size of the array being sorted and the maximum depth of the recursion tree.

The basic idea behind introsort is to take advantage of the strengths of each of the two algorithms and avoid their weaknesses. Quicksort has a very fast average-case performance and is well suited for small to medium sized arrays, but it can have a worst-case performance of O(n^2) for certain inputs. Heapsort, on the other hand, has a worst-case performance of O(n log n) but can be slower than quicksort for small arrays.

Introsort is designed to overcome the weaknesses of quicksort and heapsort by using quicksort for small arrays and switching to heapsort for larger ones. The threshold value for switching to heapsort is typically set to a value that ensures that quicksort will have good performance for most inputs, while still avoiding the worst-case behavior.

In summary, introsort combines quicksort and heapsort to achieve a fast and efficient sorting algorithm. It uses quicksort for small arrays and switches to heapsort for larger ones to avoid the worst-case performance of quicksort while maintaining its fast average-case performance.

Here given code implementation process.

// C Program 
// Sort array elements by using introsort
#include <stdio.h>

#include <math.h>

//Function which is display arr elements
void display(int arr[], int size)
{
	for (int i = 0; i < size; ++i)
	{
		printf("  %d", arr[i]);
	}
	printf("\n");
}
// Swapping the array elements in given location
void swap_data(int arr[], int first, int second)
{
	int temp = arr[first];
	arr[first] = arr[second];
	arr[second] = temp;
}
// Perform the insertion sort in given array
void insertion_sort(int arr[], int size)
{
	int i = 0;
	int j = 0;
	for (i = 0; i < size - 1; ++i)
	{
		j = i + 1;
		while (j > 0 && arr[j - 1] > arr[j])
		{
			//Swap array element
			swap_data(arr, j, j - 1);
			j--;
		}
	}
}
int partition(int arr[], int low, int high)
{
	//Set the high index element to its proper sorted position
	int pv = arr[high];
	int i = low - 1;
	for (int j = low; j < high; ++j)
	{
		if (arr[j] < pv)
		{
			i++;
			swap_data(arr, i, j);
		}
	}
	//set the high index value to its sorted position
	swap_data(arr, i + 1, high);
	//returns the next sorting  element location
	return i + 1;
}
//Perform the quick sort in given array
void quick_sort(int arr[], int low, int high)
{
	if (low < high)
	{
		//Get the pivot element
		int pv = partition(arr, low, high);
		quick_sort(arr, low, pv - 1);
		quick_sort(arr, pv + 1, high);
	}
}
int find_pivot(int arr[], int a, int b, int c)
{
	if (arr[a] < arr[b] && arr[b] < arr[c])
	{
		return b;
	}
	else if (arr[c] <= arr[b] && arr[b] <= arr[a])
	{
		return b;
	}
	else if (arr[b] < arr[c] && arr[c] <= arr[a])
	{
		return c;
	}
	else if (arr[a] < arr[c] && arr[c] <= arr[b])
	{
		return c;
	}
	else if (arr[b] <= arr[a] && arr[a] < arr[c])
	{
		return a;
	}
	else if (arr[c] <= arr[a] && arr[a] < arr[b])
	{
		return a;
	}
}
int compare(int arr[], int left, int right, int root, int size)
{
	int location = -1;
	if (left < size && arr[left] > arr[root])
	{
		if (right < size && arr[right] > arr[left])
		{
			swap_data(arr, right, root);
			location = right;
		}
		else
		{
			swap_data(arr, left, root);
			location = left;
		}
	}
	else if (right < size && arr[right] > arr[root])
	{
		swap_data(arr, right, root);
		location = right;
	}
	return location;
}
//Perform the operation of heap sort 
void heap(int arr[], int size, int root)
{
	int left, right;
	while (root != -1)
	{
		left = 2 * root + 1;
		right = 2 * root + 2;
		root = compare(arr, left, right, root, size);
	}
}
//Sort array element using heap sort
void heap_sort(int arr[], int size)
{
	for (int i = (size / 2) - 1; i >= 0; i--)
	{
		heap(arr, size, i);
	}
	for (int i = size - 1; i >= 0; i--)
	{
		swap_data(arr, 0, i);
		heap(arr, i, 0);
	}
}
//Perform the introsort in given array
void execute_introsort(int arr[], int front, int tail, int deep)
{
	int size = tail - front;
	if (size < 16)
	{
		insertion_sort(arr, tail + 1);
	}
	else if (deep == 0)
	{
		//when heap sort are work
		heap_sort(arr, tail + 1);
	}
	else
	{
		//When executed of quick sort
		int pivot = find_pivot(arr, front, front + ((tail - front) / 2) + 1, tail);
		swap_data(arr, pivot, tail);
		int point = partition(arr, front, tail);
		execute_introsort(arr, front, point - 1, deep - 1);
		execute_introsort(arr, point + 1, tail, deep - 1);
	}
}
//Handling the request of introsort
void introsort(int arr[], int size)
{
	int deep = 2 * log(size - 1);
	execute_introsort(arr, 0, size - 1, deep);
}
int main()
{
	//Define an array of integers
	int arr[] = {
		11,
		8,
		3,
		8,
		12,
		-1,
		-3,
		1,
		4,
		7,
		5
	};
	//Get the size of arr
	int size = sizeof(arr) / sizeof(arr[0]);
	//Before sort
	printf("\n  Before Sort  :\n");
	display(arr, size);
	//Sort element
	introsort(arr, size);
	//After sort
	printf("\n  After Sort  :\n");
	display(arr, size);
	int arr1[] = {
		9,
		-3,
		5,
		1,
		7,
		9,
		3,
		4,
		5,
		2,
		4,
		7,
		8,
		-4,
		6,
		34,
		43,
		2,
		7,
		8,
		11,
		12,
		9,
		-6,
		2
	};
	//Get the size of arr
	size = sizeof(arr1) / sizeof(arr1[0]);
	//Before sort
	printf("\n  Before Sort  :\n");
	display(arr1, size);
	//Sort element
	introsort(arr1, size);
	//After sort
	printf("\n  After Sort  :\n");
	display(arr1, size);
	return 0;
}

Output

  Before Sort  :
  11  8  3  8  12  -1  -3  1  4  7  5

  After Sort  :
  -3  -1  1  3  4  5  7  8  8  11  12

  Before Sort  :
  9  -3  5  1  7  9  3  4  5  2  4  7  8  -4  6  34  43  2  7  8  11  12  9  -6  2

  After Sort  :
  -6  -4  -3  1  2  2  2  3  4  4  5  5  6  7  7  7  8  8  9  9  9  11  12  34  43
/*
	Java Program
	Sort array elements by using  introsort
*/
class MySort
{
	//Function which is display arr elements
	public void display(int[] arr, int size)
	{
		for (int i = 0; i < size; ++i)
		{
			System.out.print(" " + arr[i]);
		}
		System.out.print("\n");
	}
	// Swapping the array elements in given location
	public void swap_data(int[] arr, int first, int second)
	{
		int temp = arr[first];
		arr[first] = arr[second];
		arr[second] = temp;
	}
	// Perform the insertion sort in given array
	public void insertion_sort(int[] arr, int size)
	{
		int i = 0;
		int j = 0;
		for (i = 0; i < size - 1; ++i)
		{
			j = i + 1;
			while (j > 0 && arr[j - 1] > arr[j])
			{
				//Swap array element
				swap_data(arr, j, j - 1);
				j--;
			}
		}
	}
	public int partition(int[] arr, int low, int high)
	{
		//Set the high index element to its proper sorted position
		int pv = arr[high];
		int i = low - 1;
		for (int j = low; j < high; ++j)
		{
			if (arr[j] < pv)
			{
				i++;
				swap_data(arr, i, j);
			}
		}
		//set the high index value to its sorted position
		swap_data(arr, i + 1, high);
		//returns the next sorting  element location
		return i + 1;
	}
	//Perform the quick sort in given array
	public void quick_sort(int[] arr, int low, int high)
	{
		if (low < high)
		{
			//Get the pivot element
			int pv = partition(arr, low, high);
			quick_sort(arr, low, pv - 1);
			quick_sort(arr, pv + 1, high);
		}
	}
	public int find_pivot(int[] arr, int a, int b, int c)
	{
		if (arr[a] < arr[b] && arr[b] < arr[c])
		{
			return b;
		}
		else if (arr[c] <= arr[b] && arr[b] <= arr[a])
		{
			return b;
		}
		else if (arr[b] < arr[c] && arr[c] <= arr[a])
		{
			return c;
		}
		else if (arr[a] < arr[c] && arr[c] <= arr[b])
		{
			return c;
		}
		else if (arr[b] <= arr[a] && arr[a] < arr[c])
		{
			return a;
		}
		else 
		{
			return a;
		}
	}
	public int compare(int[] arr, int left, int right, int root, int size)
	{
		int location = -1;
		if (left < size && arr[left] > arr[root])
		{
			if (right < size && arr[right] > arr[left])
			{
				swap_data(arr, right, root);
				location = right;
			}
			else
			{
				swap_data(arr, left, root);
				location = left;
			}
		}
		else if (right < size && arr[right] > arr[root])
		{
			swap_data(arr, right, root);
			location = right;
		}
		return location;
	}
	//Perform the operation of heap sort 
	public void heap(int[] arr, int size, int root)
	{
		int left, right;
		while (root != -1)
		{
			left = 2 * root + 1;
			right = 2 * root + 2;
			root = compare(arr, left, right, root, size);
		}
	}
	//Sort array element using heap sort
	public void heap_sort(int[] arr, int size)
	{
		for (int i = (size / 2) - 1; i >= 0; i--)
		{
			heap(arr, size, i);
		}
		for (int i = size - 1; i >= 0; i--)
		{
			swap_data(arr, 0, i);
			heap(arr, i, 0);
		}
	}
	//Perform the introsort in given array
	public void execute_introsort(int[] arr, int front, int tail, int deep)
	{
		int size = tail - front;
		if (size < 16)
		{
			insertion_sort(arr, tail + 1);
		}
		else if (deep == 0)
		{
			//when heap sort are work
			heap_sort(arr, tail + 1);
		}
		else
		{
			//When executed of quick sort
			int pivot = find_pivot(arr, front, front + ((tail - front) / 2) + 1, tail);
			swap_data(arr, pivot, tail);
			int point = partition(arr, front, tail);
			execute_introsort(arr, front, point - 1, deep - 1);
			execute_introsort(arr, point + 1, tail, deep - 1);
		}
	}
	//Handling the request of introsort
	public void introsort(int[] arr, int size)
	{
		int deep = (int)(2 * Math.floor(Math.log(size) / Math.log(2)));
		execute_introsort(arr, 0, size - 1, deep);
	}
	public static void main(String[] args)
	{
		MySort obj = new MySort();
		//Define an array of integers
		int[] arr = {
			11,
			8,
			3,
			8,
			12,
			-1,
			-3,
			1,
			4,
			7,
			5
		};
		//Get the size
		int size = arr.length;;
		System.out.print("\n Befre Sort :\n");
		obj.display(arr, size);
		//Sort element
		obj.introsort(arr, size);
		System.out.print("\n After Sort :\n");
		obj.display(arr, size);
		int[] arr1 = {
			9,
			-3,
			5,
			1,
			7,
			9,
			3,
			4,
			5,
			2,
			4,
			7,
			8,
			-4,
			6,
			34,
			43,
			2,
			7,
			8,
			11,
			12,
			9,
			-6,
			2
		};
		//Get the size
		size = arr1.length;
		System.out.print("\n Before Sort :\n");
		obj.display(arr1, size);
		//Sort element
		obj.introsort(arr1, size);
		System.out.print("\n After Sort :\n");
		obj.display(arr1, size);
	}
}

Output

 Befre Sort :
 11 8 3 8 12 -1 -3 1 4 7 5

 After Sort :
 -3 -1 1 3 4 5 7 8 8 11 12

 Before Sort :
 9 -3 5 1 7 9 3 4 5 2 4 7 8 -4 6 34 43 2 7 8 11 12 9 -6 2

 After Sort :
 -6 -4 -3 1 2 2 2 3 4 4 5 5 6 7 7 7 8 8 9 9 9 11 12 34 43
//Include header file
#include <iostream>

#include<math.h>

using namespace std;
/*
	C++ Program
	Sort array elements by using  introsort
*/
class MySort
{
	public:
		//Function which is display arr elements
		void display(int arr[], int size)
		{
			for (int i = 0; i < size; ++i)
			{
				cout << " " << arr[i];
			}
			cout << "\n";
		}
	// Swapping the array elements in given location
	void swap_data(int arr[], int first, int second)
	{
		int temp = arr[first];
		arr[first] = arr[second];
		arr[second] = temp;
	}
	// Perform the insertion sort in given array
	void insertion_sort(int arr[], int size)
	{
		int i = 0;
		int j = 0;
		for (i = 0; i < size - 1; ++i)
		{
			j = i + 1;
			while (j > 0 && arr[j - 1] > arr[j])
			{
				//Swap array element
				this->swap_data(arr, j, j - 1);
				j--;
			}
		}
	}
	int partition(int arr[], int low, int high)
	{
		//Set the high index element to its proper sorted position
		int pv = arr[high];
		int i = low - 1;
		for (int j = low; j < high; ++j)
		{
			if (arr[j] < pv)
			{
				i++;
				this->swap_data(arr, i, j);
			}
		}
		//set the high index value to its sorted position
		this->swap_data(arr, i + 1, high);
		//returns the next sorting  element location
		return i + 1;
	}
	//Perform the quick sort in given array
	void quick_sort(int arr[], int low, int high)
	{
		if (low < high)
		{
			//Get the pivot element
			int pv = this->partition(arr, low, high);
			this->quick_sort(arr, low, pv - 1);
			this->quick_sort(arr, pv + 1, high);
		}
	}
	int find_pivot(int arr[], int a, int b, int c)
	{
		if (arr[a] < arr[b] && arr[b] < arr[c])
		{
			return b;
		}
		else if (arr[c] <= arr[b] && arr[b] <= arr[a])
		{
			return b;
		}
		else if (arr[b] < arr[c] && arr[c] <= arr[a])
		{
			return c;
		}
		else if (arr[a] < arr[c] && arr[c] <= arr[b])
		{
			return c;
		}
		else if (arr[b] <= arr[a] && arr[a] < arr[c])
		{
			return a;
		}
		else
		{
			return a;
		}
	}
	int compare(int arr[], int left, int right, int root, int size)
	{
		int location = -1;
		if (left < size && arr[left] > arr[root])
		{
			if (right < size && arr[right] > arr[left])
			{
				this->swap_data(arr, right, root);
				location = right;
			}
			else
			{
				this->swap_data(arr, left, root);
				location = left;
			}
		}
		else if (right < size && arr[right] > arr[root])
		{
			this->swap_data(arr, right, root);
			location = right;
		}
		return location;
	}
	//Perform the operation of heap sort 
	void heap(int arr[], int size, int root)
	{
		int left, right;
		while (root != -1)
		{
			left = 2 * root + 1;
			right = 2 * root + 2;
			root = this->compare(arr, left, right, root, size);
		}
	}
	//Sort array element using heap sort
	void heap_sort(int arr[], int size)
	{
		for (int i = (size / 2) - 1; i >= 0; i--)
		{
			this->heap(arr, size, i);
		}
		for (int i = size - 1; i >= 0; i--)
		{
			this->swap_data(arr, 0, i);
			this->heap(arr, i, 0);
		}
	}
	//Perform the introsort in given array
	void execute_introsort(int arr[], int front, int tail, int deep)
	{
		int size = tail - front;
		if (size < 16)
		{
			this->insertion_sort(arr, tail + 1);
		}
		else if (deep == 0)
		{
			//when heap sort are work
			this->heap_sort(arr, tail + 1);
		}
		else
		{
			//When executed of quick sort
			int pivot = this->find_pivot(arr, front, front + ((tail - front) / 2) + 1, tail);
			this->swap_data(arr, pivot, tail);
			int point = this->partition(arr, front, tail);
			this->execute_introsort(arr, front, point - 1, deep - 1);
			this->execute_introsort(arr, point + 1, tail, deep - 1);
		}
	}
	//Handling the request of introsort
	void introsort(int arr[], int size)
	{
		int deep = (int)(2 * floor(log(size) / log(2)));
		this->execute_introsort(arr, 0, size - 1, deep);
	}
};
int main()
{
	MySort obj = MySort();
	int arr[] = {
		11 , 8 , 3 , 8 , 12 , -1 , -3 , 1 , 4 , 7 , 5
	};
	//Get the size
	int size = sizeof(arr) / sizeof(arr[0]);;
	cout << "\n Befre Sort :\n";
	obj.display(arr, size);
	//Sort element
	obj.introsort(arr, size);
	cout << "\n After Sort :\n";
	obj.display(arr, size);
	int arr1[] = {
		9 , -3 , 5 , 1 , 7 , 9 , 3 , 4 , 5 , 2 , 4 , 7 , 8 , -4 , 6 , 34 , 43 , 2 , 7 , 8 , 11 , 12 , 9 , -6 , 2
	};
	//Get the size
	size = sizeof(arr1) / sizeof(arr1[0]);
	cout << "\n Before Sort :\n";
	obj.display(arr1, size);
	//Sort element
	obj.introsort(arr1, size);
	cout << "\n After Sort :\n";
	obj.display(arr1, size);
	return 0;
}

Output

 Befre Sort :
 11 8 3 8 12 -1 -3 1 4 7 5

 After Sort :
 -3 -1 1 3 4 5 7 8 8 11 12

 Before Sort :
 9 -3 5 1 7 9 3 4 5 2 4 7 8 -4 6 34 43 2 7 8 11 12 9 -6 2

 After Sort :
 -6 -4 -3 1 2 2 2 3 4 4 5 5 6 7 7 7 8 8 9 9 9 11 12 34 43
//Include namespace system
using System;
/*
	C# Program
	Sort array elements by using  introsort
*/
class MySort
{
	//Function which is display arr elements
	public void display(int[] arr, int size)
	{
		for (int i = 0; i < size; ++i)
		{
			Console.Write(" " + arr[i]);
		}
		Console.Write("\n");
	}
	// Swapping the array elements in given location
	public void swap_data(int[] arr, int first, int second)
	{
		int temp = arr[first];
		arr[first] = arr[second];
		arr[second] = temp;
	}
	// Perform the insertion sort in given array
	public void insertion_sort(int[] arr, int size)
	{
		int i = 0;
		int j = 0;
		for (i = 0; i < size - 1; ++i)
		{
			j = i + 1;
			while (j > 0 && arr[j - 1] > arr[j])
			{
				//Swap array element
				swap_data(arr, j, j - 1);
				j--;
			}
		}
	}
	public int partition(int[] arr, int low, int high)
	{
		//Set the high index element to its proper sorted position
		int pv = arr[high];
		int i = low - 1;
		for (int j = low; j < high; ++j)
		{
			if (arr[j] < pv)
			{
				i++;
				swap_data(arr, i, j);
			}
		}
		//set the high index value to its sorted position
		swap_data(arr, i + 1, high);
		//returns the next sorting  element location
		return i + 1;
	}
	//Perform the quick sort in given array
	public void quick_sort(int[] arr, int low, int high)
	{
		if (low < high)
		{
			//Get the pivot element
			int pv = partition(arr, low, high);
			quick_sort(arr, low, pv - 1);
			quick_sort(arr, pv + 1, high);
		}
	}
	public int find_pivot(int[] arr, int a, int b, int c)
	{
		if (arr[a] < arr[b] && arr[b] < arr[c])
		{
			return b;
		}
		else if (arr[c] <= arr[b] && arr[b] <= arr[a])
		{
			return b;
		}
		else if (arr[b] < arr[c] && arr[c] <= arr[a])
		{
			return c;
		}
		else if (arr[a] < arr[c] && arr[c] <= arr[b])
		{
			return c;
		}
		else if (arr[b] <= arr[a] && arr[a] < arr[c])
		{
			return a;
		}
		else
		{
			return a;
		}
	}
	public int compare(int[] arr, int left, int right, int root, int size)
	{
		int location = -1;
		if (left < size && arr[left] > arr[root])
		{
			if (right < size && arr[right] > arr[left])
			{
				swap_data(arr, right, root);
				location = right;
			}
			else
			{
				swap_data(arr, left, root);
				location = left;
			}
		}
		else if (right < size && arr[right] > arr[root])
		{
			swap_data(arr, right, root);
			location = right;
		}
		return location;
	}
	//Perform the operation of heap sort 
	public void heap(int[] arr, int size, int root)
	{
		int left, right;
		while (root != -1)
		{
			left = 2 * root + 1;
			right = 2 * root + 2;
			root = compare(arr, left, right, root, size);
		}
	}
	//Sort array element using heap sort
	public void heap_sort(int[] arr, int size)
	{
		for (int i = (size / 2) - 1; i >= 0; i--)
		{
			heap(arr, size, i);
		}
		for (int i = size - 1; i >= 0; i--)
		{
			swap_data(arr, 0, i);
			heap(arr, i, 0);
		}
	}
	//Perform the introsort in given array
	public void execute_introsort(int[] arr, int front, int tail, int deep)
	{
		int size = tail - front;
		if (size < 16)
		{
			insertion_sort(arr, tail + 1);
		}
		else if (deep == 0)
		{
			//when heap sort are work
			heap_sort(arr, tail + 1);
		}
		else
		{
			//When executed of quick sort
			int pivot = find_pivot(arr, front, front + ((tail - front) / 2) + 1, tail);
			swap_data(arr, pivot, tail);
			int point = partition(arr, front, tail);
			execute_introsort(arr, front, point - 1, deep - 1);
			execute_introsort(arr, point + 1, tail, deep - 1);
		}
	}
	//Handling the request of introsort
	public void introsort(int[] arr, int size)
	{
		int deep = (int)(2 * Math.Floor(Math.Log(size) / Math.Log(2)));
		execute_introsort(arr, 0, size - 1, deep);
	}
	public static void Main(String[] args)
	{
		MySort obj = new MySort();
		int[] arr = {
			11 , 8 , 3 , 8 , 12 , -1 , -3 , 1 , 4 , 7 , 5
		};
		//Get the size
		int size = arr.Length;;
		Console.Write("\n Befre Sort :\n");
		obj.display(arr, size);
		//Sort element
		obj.introsort(arr, size);
		Console.Write("\n After Sort :\n");
		obj.display(arr, size);
		int[] arr1 = {
			9 , -3 , 5 , 1 , 7 , 9 , 3 , 4 , 5 , 2 , 4 , 7 , 8 , -4 , 6 , 34 , 43 , 2 , 7 , 8 , 11 , 12 , 9 , -6 , 2
		};
		//Get the size
		size = arr1.Length;
		Console.Write("\n Before Sort :\n");
		obj.display(arr1, size);
		//Sort element
		obj.introsort(arr1, size);
		Console.Write("\n After Sort :\n");
		obj.display(arr1, size);
	}
}

Output

 Befre Sort :
 11 8 3 8 12 -1 -3 1 4 7 5

 After Sort :
 -3 -1 1 3 4 5 7 8 8 11 12

 Before Sort :
 9 -3 5 1 7 9 3 4 5 2 4 7 8 -4 6 34 43 2 7 8 11 12 9 -6 2

 After Sort :
 -6 -4 -3 1 2 2 2 3 4 4 5 5 6 7 7 7 8 8 9 9 9 11 12 34 43
<?php
/*
	Php Program
	Sort array elements by using introsort
*/
class MySort
{
	//Function which is display arr elements
	public	function display($arr, $size)
	{
		for ($i = 0; $i < $size; ++$i)
		{
			echo " ". $arr[$i];
		}
		echo "\n";
	}
	// Swapping the array elements in given location
	public	function swap_data( & $arr, $first, $second)
	{
		$temp = $arr[$first];
		$arr[$first] = $arr[$second];
		$arr[$second] = $temp;
	}
	// Perform the insertion sort in given array
	public	function insertion_sort( & $arr, $size)
	{
		$i = 0;
		$j = 0;
		for ($i = 0; $i < $size - 1; ++$i)
		{
			$j = $i + 1;
			while ($j > 0 && $arr[$j - 1] > $arr[$j])
			{
				//Swap array element
				$this->swap_data($arr, $j, $j - 1);
				$j--;
			}
		}
	}
	public	function partition( & $arr, $low, $high)
	{
		//Set the high index element to its proper sorted position
		$pv = $arr[$high];
		$i = $low - 1;
		for ($j = $low; $j < $high; ++$j)
		{
			if ($arr[$j] < $pv)
			{
				$i++;
				$this->swap_data($arr, $i, $j);
			}
		}
		//set the high index value to its sorted position
		$this->swap_data($arr, $i + 1, $high);
		//returns the next sorting  element location
		return $i + 1;
	}
	//Perform the quick sort in given array
	public	function quick_sort( & $arr, $low, $high)
	{
		if ($low < $high)
		{
			//Get the pivot element
			$pv = $this->partition($arr, $low, $high);
			$this->quick_sort($arr, $low, $pv - 1);
			$this->quick_sort($arr, $pv + 1, $high);
		}
	}
	public	function find_pivot( & $arr, $a, $b, $c)
	{
		if ($arr[$a] < $arr[$b] && $arr[$b] < $arr[$c])
		{
			return $b;
		}
		else if ($arr[$c] <= $arr[$b] && $arr[$b] <= $arr[$a])
		{
			return $b;
		}
		else if ($arr[$b] < $arr[$c] && $arr[$c] <= $arr[$a])
		{
			return $c;
		}
		else if ($arr[$a] < $arr[$c] && $arr[$c] <= $arr[$b])
		{
			return $c;
		}
		else if ($arr[$b] <= $arr[$a] && $arr[$a] < $arr[$c])
		{
			return $a;
		}
		else
		{
			return $a;
		}
	}
	public	function compare( & $arr, $left, $right, $root, $size)
	{
		$location = -1;
		if ($left < $size && $arr[$left] > $arr[$root])
		{
			if ($right < $size && $arr[$right] > $arr[$left])
			{
				$this->swap_data($arr, $right, $root);
				$location = $right;
			}
			else
			{
				$this->swap_data($arr, $left, $root);
				$location = $left;
			}
		}
		else if ($right < $size && $arr[$right] > $arr[$root])
		{
			$this->swap_data($arr, $right, $root);
			$location = $right;
		}
		return $location;
	}
	//Perform the operation of heap sort 
	public	function heap( & $arr, $size, $root)
	{
		$left;
		$right;
		while ($root != -1)
		{
			$left = 2 * $root + 1;
			$right = 2 * $root + 2;
			$root = $this->compare($arr, $left, $right, $root, $size);
		}
	}
	//Sort array element using heap sort
	public	function heap_sort( & $arr, $size)
	{
		for ($i = (intval($size / 2)) - 1; $i >= 0; $i--)
		{
			$this->heap($arr, $size, $i);
		}
		for ($i = $size - 1; $i >= 0; $i--)
		{
			$this->swap_data($arr, 0, $i);
			$this->heap($arr, $i, 0);
		}
	}
	//Perform the introsort in given array
	public	function execute_introsort( & $arr, $front, $tail, $deep)
	{
		$size = $tail - $front;
		if ($size < 16)
		{
			$this->insertion_sort($arr, $tail + 1);
		}
		else if ($deep == 0)
		{
			//when heap sort are work
			$this->heap_sort($arr, $tail + 1);
		}
		else
		{
			//When executed of quick sort
			$pivot = $this->find_pivot($arr, $front, $front + (intval(($tail - $front) / 2)) + 1, $tail);
			$this->swap_data($arr, $pivot, $tail);
			$point = $this->partition($arr, $front, $tail);
			$this->execute_introsort($arr, $front, $point - 1, $deep - 1);
			$this->execute_introsort($arr, $point + 1, $tail, $deep - 1);
		}
	}
	//Handling the request of introsort
	public	function introsort( & $arr, $size)
	{
		$deep = ((2 * floor(log($size) / log(2))));
		$this->execute_introsort($arr, 0, $size - 1, $deep);
	}
}

function main()
{
	$obj = new MySort();
	//Define an array of integers
	$arr = array(11, 8, 3, 8, 12, -1, -3, 1, 4, 7, 5);
	//Get the size
	$size = count($arr);;
	echo "\n Befre Sort :\n";
	$obj->display($arr, $size);
	//Sort element
	$obj->introsort($arr, $size);
	echo "\n After Sort :\n";
	$obj->display($arr, $size);
	$arr1 = array(9, -3, 5, 1, 7, 9, 3, 4, 5, 2, 4, 7, 8, -4, 6, 34, 43, 2, 7, 8, 11, 12, 9, -6, 2);
	//Get the size
	$size = count($arr1);
	echo "\n Before Sort :\n";
	$obj->display($arr1, $size);
	//Sort element
	$obj->introsort($arr1, $size);
	echo "\n After Sort :\n";
	$obj->display($arr1, $size);
}
main();

Output

 Befre Sort :
 11 8 3 8 12 -1 -3 1 4 7 5

 After Sort :
 -3 -1 1 3 4 5 7 8 8 11 12

 Before Sort :
 9 -3 5 1 7 9 3 4 5 2 4 7 8 -4 6 34 43 2 7 8 11 12 9 -6 2

 After Sort :
 -6 -4 -3 1 2 2 2 3 4 4 5 5 6 7 7 7 8 8 9 9 9 11 12 34 43
/*
	Node Js Program
	Sort array elements by using introsort
*/
class MySort
{
	//Function which is display arr elements
	display(arr, size)
	{
		for (var i = 0; i < size; ++i)
		{
			process.stdout.write(" " + arr[i]);
		}
		process.stdout.write("\n");
	}
	// Swapping the array elements in given location
	swap_data(arr, first, second)
	{
		var temp = arr[first];
		arr[first] = arr[second];
		arr[second] = temp;
	}
	// Perform the insertion sort in given array
	insertion_sort(arr, size)
	{
		var i = 0;
		var j = 0;
		for (i = 0; i < size - 1; ++i)
		{
			j = i + 1;
			while (j > 0 && arr[j - 1] > arr[j])
			{
				//Swap array element
				this.swap_data(arr, j, j - 1);
				j--;
			}
		}
	}
	partition(arr, low, high)
	{
		//Set the high index element to its proper sorted position
		var pv = arr[high];
		var i = low - 1;
		for (var j = low; j < high; ++j)
		{
			if (arr[j] < pv)
			{
				i++;
				this.swap_data(arr, i, j);
			}
		}
		//set the high index value to its sorted position
		this.swap_data(arr, i + 1, high);
		//returns the next sorting  element location
		return i + 1;
	}
	//Perform the quick sort in given array
	quick_sort(arr, low, high)
	{
		if (low < high)
		{
			//Get the pivot element
			var pv = this.partition(arr, low, high);
			this.quick_sort(arr, low, pv - 1);
			this.quick_sort(arr, pv + 1, high);
		}
	}
	find_pivot(arr, a, b, c)
	{
		if (arr[a] < arr[b] && arr[b] < arr[c])
		{
			return b;
		}
		else if (arr[c] <= arr[b] && arr[b] <= arr[a])
		{
			return b;
		}
		else if (arr[b] < arr[c] && arr[c] <= arr[a])
		{
			return c;
		}
		else if (arr[a] < arr[c] && arr[c] <= arr[b])
		{
			return c;
		}
		else if (arr[b] <= arr[a] && arr[a] < arr[c])
		{
			return a;
		}
		else
		{
			return a;
		}
	}
	compare(arr, left, right, root, size)
	{
		var location = -1;
		if (left < size && arr[left] > arr[root])
		{
			if (right < size && arr[right] > arr[left])
			{
				this.swap_data(arr, right, root);
				location = right;
			}
			else
			{
				this.swap_data(arr, left, root);
				location = left;
			}
		}
		else if (right < size && arr[right] > arr[root])
		{
			this.swap_data(arr, right, root);
			location = right;
		}
		return location;
	}
	//Perform the operation of heap sort 
	heap(arr, size, root)
	{
		var left;
		var right;
		while (root != -1)
		{
			left = 2 * root + 1;
			right = 2 * root + 2;
			root = this.compare(arr, left, right, root, size);
		}
	}
	//Sort array element using heap sort
	heap_sort(arr, size)
	{
		for (var i = (parseInt(size / 2)) - 1; i >= 0; i--)
		{
			this.heap(arr, size, i);
		}
		for (var i = size - 1; i >= 0; i--)
		{
			this.swap_data(arr, 0, i);
			this.heap(arr, i, 0);
		}
	}
	//Perform the introsort in given array
	execute_introsort(arr, front, tail, deep)
	{
		var size = tail - front;
		if (size < 16)
		{
			this.insertion_sort(arr, tail + 1);
		}
		else if (deep == 0)
		{
			//when heap sort are work
			this.heap_sort(arr, tail + 1);
		}
		else
		{
			//When executed of quick sort
			var pivot = this.find_pivot(arr, front, front + (parseInt((tail - front) / 2)) + 1, tail);
			this.swap_data(arr, pivot, tail);
			var point = this.partition(arr, front, tail);
			this.execute_introsort(arr, front, point - 1, deep - 1);
			this.execute_introsort(arr, point + 1, tail, deep - 1);
		}
	}
	//Handling the request of introsort
	introsort(arr, size)
	{
		var deep = ((2 * Math.floor(Math.log(size) / Math.log(2))));
		this.execute_introsort(arr, 0, size - 1, deep);
	}
}

function main()
{
	var obj = new MySort();
	//Define an array of integers
	var arr = [11, 8, 3, 8, 12, -1, -3, 1, 4, 7, 5];
	//Get the size
	var size = arr.length;;
	process.stdout.write("\n Befre Sort :\n");
	obj.display(arr, size);
	//Sort element
	obj.introsort(arr, size);
	process.stdout.write("\n After Sort :\n");
	obj.display(arr, size);
	var arr1 = [9, -3, 5, 1, 7, 9, 3, 4, 5, 2, 4, 7, 8, -4, 6, 34, 43, 2, 7, 8, 11, 12, 9, -6, 2];
	//Get the size
	size = arr1.length;
	process.stdout.write("\n Before Sort :\n");
	obj.display(arr1, size);
	//Sort element
	obj.introsort(arr1, size);
	process.stdout.write("\n After Sort :\n");
	obj.display(arr1, size);
}
main();

Output

 Befre Sort :
 11 8 3 8 12 -1 -3 1 4 7 5

 After Sort :
 -3 -1 1 3 4 5 7 8 8 11 12

 Before Sort :
 9 -3 5 1 7 9 3 4 5 2 4 7 8 -4 6 34 43 2 7 8 11 12 9 -6 2

 After Sort :
 -6 -4 -3 1 2 2 2 3 4 4 5 5 6 7 7 7 8 8 9 9 9 11 12 34 43
import math
# 
# 	Python 3 Program
# 	Sort array elements by using introsort

class MySort :
	# Function which is display arr elements
	def display(self, arr, size) :
		i = 0
		while (i < size) :
			print(" ", arr[i], end = "")
			i += 1
		
		print("\n", end = "")
	
	#  Swapping the array elements in given location
	def swap_data(self, arr, first, second) :
		temp = arr[first]
		arr[first] = arr[second]
		arr[second] = temp
	
	#  Perform the insertion sort in given array
	def insertion_sort(self, arr, size) :
		i = 0
		j = 0
		while (i < size - 1) :
			j = i + 1
			while (j > 0 and arr[j - 1] > arr[j]) :
				# Swap array element
				self.swap_data(arr, j, j - 1)
				j -= 1
			
			i += 1
		
	
	def partition(self, arr, low, high) :
		# Set the high index element to its proper sorted position
		pv = arr[high]
		i = low - 1
		j = low
		while (j < high) :
			if (arr[j] < pv) :
				i += 1
				self.swap_data(arr, i, j)
			
			j += 1
		
		# set the high index value to its sorted position
		self.swap_data(arr, i + 1, high)
		# returns the next sorting  element location
		return i + 1
	
	# Perform the quick sort in given array
	def quick_sort(self, arr, low, high) :
		if (low < high) :
			# Get the pivot element
			pv = self.partition(arr, low, high)
			self.quick_sort(arr, low, pv - 1)
			self.quick_sort(arr, pv + 1, high)
		
	
	def find_pivot(self, arr, a, b, c) :
		if (arr[a] < arr[b] and arr[b] < arr[c]) :
			return b
		
		elif(arr[c] <= arr[b] and arr[b] <= arr[a]) :
			return b
		
		elif(arr[b] < arr[c] and arr[c] <= arr[a]) :
			return c
		
		elif(arr[a] < arr[c] and arr[c] <= arr[b]) :
			return c
		
		elif(arr[b] <= arr[a] and arr[a] < arr[c]) :
			return a
		else :
			return a
		
	
	def compare(self, arr, left, right, root, size) :
		location = -1
		if (left < size and arr[left] > arr[root]) :
			if (right < size and arr[right] > arr[left]) :
				self.swap_data(arr, right, root)
				location = right
			else :
				self.swap_data(arr, left, root)
				location = left
			
		
		elif(right < size and arr[right] > arr[root]) :
			self.swap_data(arr, right, root)
			location = right
		
		return location
	
	# Perform the operation of heap sort 
	def heap(self, arr, size, root) :
		left
		right
		while (root != -1) :
			left = 2 * root + 1
			right = 2 * root + 2
			root = self.compare(arr, left, right, root, size)
		
	
	# Sort array element using heap sort
	def heap_sort(self, arr, size) :
		i = (int(size / 2)) - 1
		while (i >= 0) :
			self.heap(arr, size, i)
			i -= 1
		
		i = size - 1
		while (i >= 0) :
			self.swap_data(arr, 0, i)
			self.heap(arr, i, 0)
			i -= 1
		
	
	# Perform the introsort in given array
	def execute_introsort(self, arr, front, tail, deep) :
		size = tail - front
		if (size < 16) :
			self.insertion_sort(arr, tail + 1)
		
		elif(deep == 0) :
			# when heap sort are work
			self.heap_sort(arr, tail + 1)
		else :
			# When executed of quick sort
			pivot = self.find_pivot(arr, front, front + (int((tail - front) / 2)) + 1, tail)
			self.swap_data(arr, pivot, tail)
			point = self.partition(arr, front, tail)
			self.execute_introsort(arr, front, point - 1, deep - 1)
			self.execute_introsort(arr, point + 1, tail, deep - 1)
		
	
	# Handling the request of introsort
	def introsort(self, arr, size) :
		deep = ((2 * math.floor(int(math.log(size) / math.log(2)))))
		self.execute_introsort(arr, 0, size - 1, deep)
	

def main() :
	obj = MySort()
	# Define an array of integers
	arr = [11, 8, 3, 8, 12, -1, -3, 1, 4, 7, 5]
	# Get the size
	size = len(arr)
	print("\n Befre Sort :\n", end = "")
	obj.display(arr, size)
	# Sort element
	obj.introsort(arr, size)
	print("\n After Sort :\n", end = "")
	obj.display(arr, size)
	arr1 = [9, -3, 5, 1, 7, 9, 3, 4, 5, 2, 4, 7, 8, -4, 6, 34, 43, 2, 7, 8, 11, 12, 9, -6, 2]
	# Get the size
	size = len(arr1)
	print("\n Before Sort :\n", end = "")
	obj.display(arr1, size)
	# Sort element
	obj.introsort(arr1, size)
	print("\n After Sort :\n", end = "")
	obj.display(arr1, size)

if __name__ == "__main__": main()

Output

 Befre Sort :
  11  8  3  8  12  -1  -3  1  4  7  5

 After Sort :
  -3  -1  1  3  4  5  7  8  8  11  12

 Before Sort :
  9  -3  5  1  7  9  3  4  5  2  4  7  8  -4  6  34  43  2  7  8  11  12  9  -6  2

 After Sort :
  -6  -4  -3  1  2  2  2  3  4  4  5  5  6  7  7  7  8  8  9  9  9  11  12  34  43
# 	Ruby Program
# 	Sort array elements by using introsort

class MySort

	# Function which is display arr elements
	def display(arr, size)
	
		i = 0
		while (i < size)
		
			print(" ", arr[i])
			i += 1
		end
		print("\n")
	end
	#  Swapping the array elements in given location
	def swap_data(arr, first, second)
	
		temp = arr[first]
		arr[first] = arr[second]
		arr[second] = temp
	end
	#  Perform the insertion sort in given array
	def insertion_sort(arr, size)
	
		i = 0
		j = 0
		while (i < size - 1)
		
			j = i + 1
			while (j > 0 && arr[j - 1] > arr[j])
			
				# Swap array element
				self.swap_data(arr, j, j - 1)
				j -= 1
			end
			i += 1
		end
	end
	def partition(arr, low, high)
	
		# Set the high index element to its proper sorted position
		pv = arr[high]
		i = low - 1
		j = low
		while (j < high)
		
			if (arr[j] < pv)
			
				i += 1
				self.swap_data(arr, i, j)
			end
			j += 1
		end
		# set the high index value to its sorted position
		self.swap_data(arr, i + 1, high)
		# returns the next sorting  element location
		return i + 1
	end
	# Perform the quick sort in given array
	def quick_sort(arr, low, high)
	
		if (low < high)
		
			# Get the pivot element
			pv = self.partition(arr, low, high)
			self.quick_sort(arr, low, pv - 1)
			self.quick_sort(arr, pv + 1, high)
		end
	end
	def find_pivot(arr, a, b, c)
	
		if (arr[a] < arr[b] && arr[b] < arr[c])
		
			return b
		elsif(arr[c] <= arr[b] && arr[b] <= arr[a])
		
			return b
		elsif(arr[b] < arr[c] && arr[c] <= arr[a])
		
			return c
		elsif(arr[a] < arr[c] && arr[c] <= arr[b])
		
			return c
		elsif(arr[b] <= arr[a] && arr[a] < arr[c])
		
			return a
		else
		
			return a
		end
	end
	def compare(arr, left, right, root, size)
	
		location = -1
		if (left < size && arr[left] > arr[root])
		
			if (right < size && arr[right] > arr[left])
			
				self.swap_data(arr, right, root)
				location = right
			else
			
				self.swap_data(arr, left, root)
				location = left
			end
		elsif(right < size && arr[right] > arr[root])
		
			self.swap_data(arr, right, root)
			location = right
		end
		return location
	end
	# Perform the operation of heap sort 
	def heap(arr, size, root)
	
		left
		right
		while (root != -1)
		
			left = 2 * root + 1
			right = 2 * root + 2
			root = self.compare(arr, left, right, root, size)
		end
	end
	# Sort array element using heap sort
	def heap_sort(arr, size)
	
		i = (size / 2) - 1
		while (i >= 0)
		
			self.heap(arr, size, i)
			i -= 1
		end
		i = size - 1
		while (i >= 0)
		
			self.swap_data(arr, 0, i)
			self.heap(arr, i, 0)
			i -= 1
		end
	end
	# Perform the introsort in given array
	def execute_introsort(arr, front, tail, deep)
	
		size = tail - front
		if (size < 16)
		
			self.insertion_sort(arr, tail + 1)
		elsif(deep == 0)
		
			# when heap sort are work
			self.heap_sort(arr, tail + 1)
		else
		
			# When executed of quick sort
			pivot = self.find_pivot(arr, front, front + ((tail - front) / 2) + 1, tail)
			self.swap_data(arr, pivot, tail)
			point = self.partition(arr, front, tail)
			self.execute_introsort(arr, front, point - 1, deep - 1)
			self.execute_introsort(arr, point + 1, tail, deep - 1)
		end
	end
	# Handling the request of introsort
	def introsort(arr, size)
	
		deep = (2 * (Math.log(size) / Math.log(2)).floor).to_i
		self.execute_introsort(arr, 0, size - 1, deep)
	end
end
def main()

	obj = MySort.new()
	# Define an array of integers
	arr = [11, 8, 3, 8, 12, -1, -3, 1, 4, 7, 5]
	# Get the size
	size = arr.length
	print("\n Befre Sort :\n")
	obj.display(arr, size)
	# Sort element
	obj.introsort(arr, size)
	print("\n After Sort :\n")
	obj.display(arr, size)
	arr1 = [9, -3, 5, 1, 7, 9, 3, 4, 5, 2, 4, 7, 8, -4, 6, 34, 43, 2, 7, 8, 11, 12, 9, -6, 2]
	# Get the size
	size = arr1.length
	print("\n Before Sort :\n")
	obj.display(arr1, size)
	# Sort element
	obj.introsort(arr1, size)
	print("\n After Sort :\n")
	obj.display(arr1, size)
end
main()

Output

 Befre Sort :
 11 8 3 8 12 -1 -3 1 4 7 5

 After Sort :
 -3 -1 1 3 4 5 7 8 8 11 12

 Before Sort :
 9 -3 5 1 7 9 3 4 5 2 4 7 8 -4 6 34 43 2 7 8 11 12 9 -6 2

 After Sort :
 -6 -4 -3 1 2 2 2 3 4 4 5 5 6 7 7 7 8 8 9 9 9 11 12 34 43

/*
	Scala Program
	Sort array elements by using introsort
*/
class MySort
{
	//Function which is display arr elements
	def display(arr: Array[Int], size: Int): Unit = {
		var i: Int = 0;
		while (i < size)
		{
			print(" " + arr(i));
			i += 1;
		}
		print("\n");
	}
	// Swapping the array elements in given location
	def swap_data(arr: Array[Int], first: Int, second: Int): Unit = {
		var temp: Int = arr(first);
		arr(first) = arr(second);
		arr(second) = temp;
	}
	// Perform the insertion sort in given array
	def insertion_sort(arr: Array[Int], size: Int): Unit = {
		var i: Int = 0;
		var j: Int = 0;
		while (i < size - 1)
		{
			j = i + 1;
			while (j > 0 && arr(j - 1) > arr(j))
			{
				//Swap array element
				swap_data(arr, j, j - 1);
				j -= 1;
			}
			i += 1;
		}
	}
	def partition(arr: Array[Int], low: Int, high: Int): Int = {
		//Set the high index element to its proper sorted position
		var pv: Int = arr(high);
		var i: Int = low - 1;
		var j: Int = low;
		while (j < high)
		{
			if (arr(j) < pv)
			{
				i += 1;
				swap_data(arr, i, j);
			}
			j += 1;
		}
		//set the high index value to its sorted position
		swap_data(arr, i + 1, high);
		//returns the next sorting  element location
		return i + 1;
	}
	//Perform the quick sort in given array
	def quick_sort(arr: Array[Int], low: Int, high: Int): Unit = {
		if (low < high)
		{
			//Get the pivot element
			var pv: Int = partition(arr, low, high);
			quick_sort(arr, low, pv - 1);
			quick_sort(arr, pv + 1, high);
		}
	}
	def find_pivot(arr: Array[Int], a: Int, b: Int, c: Int): Int = {
		if (arr(a) < arr(b) && arr(b) < arr(c))
		{
			return b;
		}
		else if (arr(c) <= arr(b) && arr(b) <= arr(a))
		{
			return b;
		}
		else if (arr(b) < arr(c) && arr(c) <= arr(a))
		{
			return c;
		}
		else if (arr(a) < arr(c) && arr(c) <= arr(b))
		{
			return c;
		}
		else if (arr(b) <= arr(a) && arr(a) < arr(c))
		{
			return a;
		}
		else
		{
			return a;
		}
	}
	def compare(arr: Array[Int], left: Int, right: Int, root: Int, size: Int): Int = {
		var location: Int = -1;
		if (left < size && arr(left) > arr(root))
		{
			if (right < size && arr(right) > arr(left))
			{
				swap_data(arr, right, root);
				location = right;
			}
			else
			{
				swap_data(arr, left, root);
				location = left;
			}
		}
		else if (right < size && arr(right) > arr(root))
		{
			swap_data(arr, right, root);
			location = right;
		}
		return location;
	}
	//Perform the operation of heap sort 
	def heap(arr: Array[Int], size: Int, root: Int): Unit = {
		var left: Int = 0;
		var right: Int = 0;
        var location = root;
		while (location != -1)
		{
			left = 2 * location + 1;
			right = 2 * location + 2;
			location = compare(arr, left, right, location, size);
		}
	}
	//Sort array element using heap sort
	def heap_sort(arr: Array[Int], size: Int): Unit = {
		var i: Int = ((size / 2).toInt) - 1;
		while (i >= 0)
		{
			heap(arr, size, i);
			i -= 1;
		}
		i = size - 1;
		while (i >= 0)
		{
			swap_data(arr, 0, i);
			heap(arr, i, 0);
			i -= 1;
		}
	}
	//Perform the introsort in given array
	def execute_introsort(arr: Array[Int], front: Int, tail: Int, deep: Int): Unit = {
		var size: Int = tail - front;
		if (size < 16)
		{
			insertion_sort(arr, tail + 1);
		}
		else if (deep == 0)
		{
			//when heap sort are work
			heap_sort(arr, tail + 1);
		}
		else
		{
			//When executed of quick sort
			var pivot: Int = find_pivot(arr, front, front + (((tail - front) / 2).toInt) + 1, tail);
			swap_data(arr, pivot, tail);
			var point: Int = partition(arr, front, tail);
			execute_introsort(arr, front, point - 1, deep - 1);
			execute_introsort(arr, point + 1, tail, deep - 1);
		}
	}
	//Handling the request of introsort
	def introsort(arr: Array[Int], size: Int): Unit = {
		val deep : Int = (2 * Math.floor(Math.log(size) / Math.log(2))).toInt;
		execute_introsort(arr, 0, size - 1, deep);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: MySort = new MySort();
		//Define an array of integers
		var arr: Array[Int] = Array(11, 8, 3, 8, 12, -1, -3, 1, 4, 7, 5);
		//Get the size
		var size: Int = arr.length;
		print("\n Befre Sort :\n");
		obj.display(arr, size);
		//Sort element
		obj.introsort(arr, size);
		print("\n After Sort :\n");
		obj.display(arr, size);
		var arr1: Array[Int] = Array(9, -3, 5, 1, 7, 9, 3, 4, 5, 2, 4, 7, 8, -4, 6, 34, 43, 2, 7, 8, 11, 12, 9, -6, 2);
		//Get the size
		size = arr1.length;
		print("\n Before Sort :\n");
		obj.display(arr1, size);
		//Sort element
		obj.introsort(arr1, size);
		print("\n After Sort :\n");
		obj.display(arr1, size);
	}
}

Output

 Befre Sort :
 11 8 3 8 12 -1 -3 1 4 7 5

 After Sort :
 -3 -1 1 3 4 5 7 8 8 11 12

 Before Sort :
 9 -3 5 1 7 9 3 4 5 2 4 7 8 -4 6 34 43 2 7 8 11 12 9 -6 2

 After Sort :
 -6 -4 -3 1 2 2 2 3 4 4 5 5 6 7 7 7 8 8 9 9 9 11 12 34 43
import Foundation
/*
	Swift Program
	Sort array elements by using introsort
*/
class MySort
{
	//Function which is display arr elements
	func display(_ arr: [Int], _ size: Int)
	{
		var i: Int = 0;
		while (i < size)
		{
			print(" ", arr[i], terminator: "");
			i += 1;
		}
		print(terminator: "\n");
	}
	// Swapping the array elements in given location
	func swap_data(_ arr: inout[Int], _ first: Int, _ second: Int)
	{
		let temp: Int = arr[first];
		arr[first] = arr[second];
		arr[second] = temp;
	}
	// Perform the insertion sort in given array
	func insertion_sort(_ arr:inout [Int], _ size: Int)
	{
		var i: Int = 0;
		var j: Int = 0;
		while (i < size - 1)
		{
			j = i + 1;
			while (j > 0 && arr[j - 1] > arr[j])
			{
				//Swap array element
				self.swap_data(&arr, j, j - 1);
				j -= 1;
			}
			i += 1;
		}
	}
	func partition(_ arr: inout[Int], _ low: Int, _ high: Int) -> Int
	{
		//Set the high index element to its proper sorted position
		let pv: Int = arr[high];
		var i: Int = low - 1;
		var j: Int = low;
		while (j < high)
		{
			if (arr[j] < pv)
			{
				i += 1;
				self.swap_data(&arr, i, j);
			}
			j += 1;
		}
		//set the high index value to its sorted position
		self.swap_data(&arr, i + 1, high);
		//returns the next sorting  element location
		return i + 1;
	}
	//Perform the quick sort in given array
	func quick_sort(_ arr: inout[Int], _ low: Int, _ high: Int)
	{
		if (low < high)
		{
			//Get the pivot element
			let pv: Int = self.partition(&arr, low, high);
			self.quick_sort(&arr, low, pv - 1);
			self.quick_sort(&arr, pv + 1, high);
		}
	}
	func find_pivot(_ arr: [Int], _ a: Int, _ b: Int, _ c: Int) -> Int
	{
		if (arr[a] < arr[b] && arr[b] < arr[c])
		{
			return b;
		}
		else if (arr[c] <= arr[b] && arr[b] <= arr[a])
		{
			return b;
		}
		else if (arr[b] < arr[c] && arr[c] <= arr[a])
		{
			return c;
		}
		else if (arr[a] < arr[c] && arr[c] <= arr[b])
		{
			return c;
		}
		else if (arr[b] <= arr[a] && arr[a] < arr[c])
		{
			return a;
		}
		else
		{
			return a;
		}
	}
	func compare(_ arr: inout[Int], _ left: Int, _ right: Int, _ root: Int, _ size: Int) -> Int
	{
		var location: Int = -1;
		if (left < size && arr[left] > arr[root])
		{
			if (right < size && arr[right] > arr[left])
			{
				self.swap_data(&arr, right, root);
				location = right;
			}
			else
			{
				self.swap_data(&arr, left, root);
				location = left;
			}
		}
		else if (right < size && arr[right] > arr[root])
		{
			self.swap_data(&arr, right, root);
			location = right;
		}
		return location;
	}
	//Perform the operation of heap sort 
	func heap(_ arr: inout[Int], _ size: Int, _ root:  Int)
	{
		var left: Int;
		var right: Int;
      	var location : Int = root;
		while (location != -1)
		{
			left = 2 * location + 1;
			right = 2 * location + 2;
			location = self.compare(&arr, left, right, location, size);
		}
	}
	//Sort array element using heap sort
	func heap_sort(_ arr: inout[Int], _ size: Int)
	{
		var i: Int = (size / 2) - 1;
		while (i >= 0)
		{
			self.heap(&arr, size, i);
			i -= 1;
		}
		i = size - 1;
		while (i >= 0)
		{
			self.swap_data(&arr, 0, i);
			self.heap(&arr, i, 0);
			i -= 1;
		}
	}
	//Perform the introsort in given array
	func execute_introsort(_ arr: inout [Int], _ front: Int, _ tail: Int, _ deep: Int)
	{
		let size: Int = tail - front;
		if (size < 16)
		{
			self.insertion_sort(&arr, tail + 1);
		}
		else if (deep == 0)
		{
			//when heap sort are work
			self.heap_sort(&arr, tail + 1);
		}
		else
		{
			//When executed of quick sort
			let pivot: Int = self.find_pivot(arr, front, front + ((tail - front) / 2) + 1, tail);
			self.swap_data(&arr, pivot, tail);
			let point: Int = self.partition(&arr, front, tail);
			self.execute_introsort(&arr, front, point - 1, deep - 1);
			self.execute_introsort(&arr, point + 1, tail, deep - 1);
		}
	}
	//Handling the request of introsort
	func introsort(_ arr: inout[Int], _ size: Int)
	{
		let deep: Int = Int(2 * log2(Double(size)));
	self.execute_introsort(&arr, 0, size - 1, deep);
}
}
func main()
{
	let obj: MySort = MySort();
	//Define an array of integers
	var arr: [Int] = [11, 8, 3, 8, 12, -1, -3, 1, 4, 7, 5];
	//Get the size
	var size: Int = arr.count;
	print("\n Befre Sort :");
	obj.display(arr, size);
	//Sort element
	obj.introsort(&arr, size);
	print("\n After Sort :");
	obj.display(arr, size);
	var arr1: [Int] = [9, -3, 5, 1, 7, 9, 3, 4, 5, 2, 4, 7, 8, -4, 6, 34, 43, 2, 7, 8, 11, 12, 9, -6, 2];
	//Get the size
	size = arr1.count;
	print("\n Before Sort :");
	obj.display(arr1, size);
	//Sort element
	obj.introsort(&arr1, size);
	print("\n After Sort :");
	obj.display(arr1, size);
}
main();

Output

 Befre Sort :
  11  8  3  8  12  -1  -3  1  4  7  5

 After Sort :
  -3  -1  1  3  4  5  7  8  8  11  12

 Before Sort :
  9  -3  5  1  7  9  3  4  5  2  4  7  8  -4  6  34  43  2  7  8  11  12  9  -6  2

 After Sort :
  -6  -4  -3  1  2  2  2  3  4  4  5  5  6  7  7  7  8  8  9  9  9  11  12  34  43
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment