Skip to main content

Bitonic Sort

Bitonic sort is a sorting algorithm that is used to sort a sequence of elements in ascending or descending order. It is a highly parallelizable sorting algorithm that is widely used in computer science and engineering, particularly in the field of signal processing and digital signal processing.

The algorithm is based on the concept of a "bitonic sequence," which is a sequence of numbers that first monotonically increases and then monotonically decreases. The key idea behind the bitonic sort algorithm is to take an input sequence of n elements and recursively divide it into smaller bitonic sequences. These bitonic sequences are then sorted in ascending order or descending order, depending on the desired output.

The bitonic sort algorithm is efficient and has a time complexity of O(n*log^2(n)). It can be implemented using parallel hardware, such as GPUs or FPGAs, which makes it a popular choice for high-performance computing applications. However, the algorithm is not as commonly used as other sorting algorithms such as quicksort or mergesort, due to its complexity and specialized use cases.

Here given code implementation process.

// C Program 
// Sort array elements by using bitonic sort
// Given program are perfectly work when given input array size have equal to power of 2
#include <stdio.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");
}
void merge_element(int arr[], int low, int high, int order)
{
	if (high > 1)
	{
		int position = high / 2;
		int temp = 0;
		int j = 0;
		//Loop controlling variable
		int i = 0;
		for (i = low; i < low + position; i++)
		{
			j = i + position;
			if ((order == 1 && arr[i] > arr[j]) || (order == 0 && arr[i] < arr[j]))
			{
				//Interchange the elements
				temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		}
		merge_element(arr, low, position, order);
		merge_element(arr, low + position, position, order);
	}
}
//produce bitonic sequence and sorted combine its elements
void bitonic_sort(int arr[], int low, int high, int order)
{
	if (high > 1)
	{
		int position = high / 2;
		// sort element in ascending order 
		bitonic_sort(arr, low, position, 1);
		// sort element in descending order
		bitonic_sort(arr, low + position, position, 0);
		// merge equence in ascending order 
		merge_element(arr, low, high, order);
	}
}
void sort_element(int arr[], int size)
{
	bitonic_sort(arr, 0, size, 1);
}
int main()
{
	//Define an array of integers
	int arr1[] = {
		3,
		6,
		2,
		5,
		-7,
		2,
		1,
		4
	};
	//Get the size of arr
	int size = sizeof(arr1) / sizeof(arr1[0]);
	//Before sort
	printf("\n  Before Sort  :\n");
	display(arr1, size);
	//Sort element
	sort_element(arr1, size);
	//After sort
	printf("\n  After Sort  :\n");
	display(arr1, size);
	//Given array have 2^4 elements
	int arr2[] = {
		8,
		2,
		9,
		-6,
		3,
		2,
		31,
		41,
		2,
		1,
		67,
		32,
		24,
		21,
		4,
		5
	};
	//Get the size of arr
	size = sizeof(arr2) / sizeof(arr2[0]);
	//Before sort
	printf("\n  Before Sort  :\n");
	display(arr2, size);
	//Sort element
	sort_element(arr2, size);
	//After sort
	printf("\n  After Sort  :\n");
	display(arr2, size);
	return 0;
}

Output

  Before Sort  :
  3  6  2  5  -7  2  1  4

  After Sort  :
  -7  1  2  2  3  4  5  6

  Before Sort  :
  8  2  9  -6  3  2  31  41  2  1  67  32  24  21  4  5

  After Sort  :
  -6  1  2  2  2  3  4  5  8  9  21  24  31  32  41  67
// Java Program 
// Sort array elements by using bitonic sort
// Given program are perfectly work when given input array size have equal to power of 2

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");
	}
	public void merge_element(int[] arr, int low, int high, int order)
	{
		if (high > 1)
		{
			int position = high / 2;
			int temp = 0;
			int j = 0;
			//Loop controlling variable
			int i = 0;
			for (i = low; i < low + position; i++)
			{
				j = i + position;
				if ((order == 1 && arr[i] > arr[j]) || (order == 0 && arr[i] < arr[j]))
				{
				//Interchange the elements
					temp = arr[i];
					arr[i] = arr[j];
					arr[j] = temp;
				}
			}
			merge_element(arr, low, position, order);
			merge_element(arr, low + position, position, order);
		}
	}
	//produce bitonic sequence and sorted combine its elements
	public void bitonic_sort(int[] arr, int low, int high, int order)
	{
		if (high > 1)
		{
			int position = high / 2;
		// sort element in ascending order 
			bitonic_sort(arr, low, position, 1);
		// sort element in descending order
			bitonic_sort(arr, low + position, position, 0);
		// merge equence in ascending order 
			merge_element(arr, low, high, order);
		}
	}
	public void sort_element(int[] arr, int size)
	{
		bitonic_sort(arr, 0, size, 1);
	}
	public static void main(String[] args) {
		MySort obj = new MySort();


        //Define an array of integers
		int[] arr1 =  {
			3 , 6 , 2 , 5 , -7 , 2 , 1 , 4
		};
		//Get the size of arr
		int size = arr1.length;
		System.out.print("\n Before Sort :\n");
		obj.display(arr1, size);
		//Sort element
		obj.sort_element(arr1, size);
		System.out.print("\n After Sort :\n");
		obj.display(arr1, size);
		//Given array have 2^4 elements
		int[] arr2 =  {
			8 , 2 , 9 , -6 , 3 , 2 , 31 , 41 , 2 , 1 , 67 , 32 , 24 , 21 , 4 , 5
		};
		//Get the size of arr
		size = arr2.length;
		System.out.print("\n Before Sort :\n");
		obj.display(arr2, size);
		//Sort element
		obj.sort_element(arr2, size);
		System.out.print("\n After Sort :\n");
		obj.display(arr2, size);
	}
}

Output

 Before Sort :
 3 6 2 5 -7 2 1 4

 After Sort :
 -7 1 2 2 3 4 5 6

 Before Sort :
 8 2 9 -6 3 2 31 41 2 1 67 32 24 21 4 5

 After Sort :
 -6 1 2 2 2 3 4 5 8 9 21 24 31 32 41 67
//Include header file
#include <iostream>
using namespace std;

// C++ Program 
// Sort array elements by using bitonic sort
// Given program are perfectly work when given input array size have equal to power of 2
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";
		}
	void merge_element(int arr[], int low, int high, int order)
	{
		if (high > 1)
		{
			int position = high / 2;
			int temp = 0;
			int j = 0;
			//Loop controlling variable
			int i = 0;
			for (i = low; i < low + position; i++)
			{
				j = i + position;
				if ((order == 1 && arr[i] > arr[j]) || (order == 0 && arr[i] < arr[j]))
				{
					//Interchange the elements
					temp = arr[i];
					arr[i] = arr[j];
					arr[j] = temp;
				}
			}
			this->merge_element(arr, low, position, order);
			this->merge_element(arr, low + position, position, order);
		}
	}
	//produce bitonic sequence and sorted combine its elements
	void bitonic_sort(int arr[], int low, int high, int order)
	{
		if (high > 1)
		{
			int position = high / 2;
			// sort element in ascending order 
			this->bitonic_sort(arr, low, position, 1);
			// sort element in descending order
			this->bitonic_sort(arr, low + position, position, 0);
			// merge equence in ascending order 
			this->merge_element(arr, low, high, order);
		}
	}
	void sort_element(int arr[], int size)
	{
		this->bitonic_sort(arr, 0, size, 1);
	}
};
int main()
{
	MySort obj = MySort();
	int arr1[] = {
		3 , 6 , 2 , 5 , -7 , 2 , 1 , 4
	};
	//Get the size of arr
	int size = sizeof(arr1) / sizeof(arr1[0]);
	cout << "\n Before Sort :\n";
	obj.display(arr1, size);
	//Sort element
	obj.sort_element(arr1, size);
	cout << "\n After Sort :\n";
	obj.display(arr1, size);
	int arr2[] = {
		8 , 2 , 9 , -6 , 3 , 2 , 31 , 41 , 2 , 1 , 67 , 32 , 24 , 21 , 4 , 5
	};
	//Get the size of arr
	size = sizeof(arr2) / sizeof(arr2[0]);
	cout << "\n Before Sort :\n";
	obj.display(arr2, size);
	//Sort element
	obj.sort_element(arr2, size);
	cout << "\n After Sort :\n";
	obj.display(arr2, size);
	return 0;
}

Output

 Before Sort :
 3 6 2 5 -7 2 1 4

 After Sort :
 -7 1 2 2 3 4 5 6

 Before Sort :
 8 2 9 -6 3 2 31 41 2 1 67 32 24 21 4 5

 After Sort :
 -6 1 2 2 2 3 4 5 8 9 21 24 31 32 41 67
//Include namespace system
using System;
// C# Program 
// Sort array elements by using bitonic sort
// Given program are perfectly work when given input array size have equal to power of 2
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");
	}
	public void merge_element(int[] arr, int low, int high, int order)
	{
		if (high > 1)
		{
			int position = high / 2;
			int temp = 0;
			int j = 0;
			//Loop controlling variable
			int i = 0;
			for (i = low; i < low + position; i++)
			{
				j = i + position;
				if ((order == 1 && arr[i] > arr[j]) || (order == 0 && arr[i] < arr[j]))
				{
					//Interchange the elements
					temp = arr[i];
					arr[i] = arr[j];
					arr[j] = temp;
				}
			}
			merge_element(arr, low, position, order);
			merge_element(arr, low + position, position, order);
		}
	}
	//produce bitonic sequence and sorted combine its elements
	public void bitonic_sort(int[] arr, int low, int high, int order)
	{
		if (high > 1)
		{
			int position = high / 2;
			// sort element in ascending order 
			bitonic_sort(arr, low, position, 1);
			// sort element in descending order
			bitonic_sort(arr, low + position, position, 0);
			// merge equence in ascending order 
			merge_element(arr, low, high, order);
		}
	}
	public void sort_element(int[] arr, int size)
	{
		bitonic_sort(arr, 0, size, 1);
	}
	public static void Main(String[] args)
	{
		MySort obj = new MySort();
		int[] arr1 = {
			3 , 6 , 2 , 5 , -7 , 2 , 1 , 4
		};
		//Get the size of arr
		int size = arr1.Length;
		Console.Write("\n Before Sort :\n");
		obj.display(arr1, size);
		//Sort element
		obj.sort_element(arr1, size);
		Console.Write("\n After Sort :\n");
		obj.display(arr1, size);
		int[] arr2 = {
			8 , 2 , 9 , -6 , 3 , 2 , 31 , 41 , 2 , 1 , 67 , 32 , 24 , 21 , 4 , 5
		};
		//Get the size of arr
		size = arr2.Length;
		Console.Write("\n Before Sort :\n");
		obj.display(arr2, size);
		//Sort element
		obj.sort_element(arr2, size);
		Console.Write("\n After Sort :\n");
		obj.display(arr2, size);
	}
}

Output

 Before Sort :
 3 6 2 5 -7 2 1 4

 After Sort :
 -7 1 2 2 3 4 5 6

 Before Sort :
 8 2 9 -6 3 2 31 41 2 1 67 32 24 21 4 5

 After Sort :
 -6 1 2 2 2 3 4 5 8 9 21 24 31 32 41 67
<?php
// Php Program 
// Sort array elements by using bitonic sort
// Given program are perfectly work when given input array size have equal to power of 2
class MySort
{
	//Function which is display arr elements
	public	function display( $arr, $size)
	{
		for ($i = 0; $i < $size; ++$i)
		{
			echo " ". $arr[$i];
		}
		echo "\n";
	}
	public	function merge_element( & $arr, $low, $high, $order)
	{
		if ($high > 1)
		{
			$position = intval($high / 2);
			$temp = 0;
			$j = 0;
			//Loop controlling variable
			$i = 0;
			for ($i = $low; $i < $low + $position; $i++)
			{
				$j = $i + $position;
				if (($order == 1 && $arr[$i] > $arr[$j]) || ($order == 0 && $arr[$i] < $arr[$j]))
				{
					//Interchange the elements
					$temp = $arr[$i];
					$arr[$i] = $arr[$j];
					$arr[$j] = $temp;
				}
			}
			$this->merge_element($arr, $low, $position, $order);
			$this->merge_element($arr, $low + $position, $position, $order);
		}
	}
	//produce bitonic sequence and sorted combine its elements
	public	function bitonic_sort( & $arr, $low, $high, $order)
	{
		if ($high > 1)
		{
			$position = intval($high / 2);
			// sort element in ascending order 
			$this->bitonic_sort($arr, $low, $position, 1);
			// sort element in descending order
			$this->bitonic_sort($arr, $low + $position, $position, 0);
			// merge equence in ascending order 
			$this->merge_element($arr, $low, $high, $order);
		}
	}
	public	function sort_element( & $arr, $size)
	{
		$this->bitonic_sort($arr, 0, $size, 1);
	}
}

function main()
{
	$obj = new MySort();
	//Define an array of integers
	$arr1 = array(3, 6, 2, 5, -7, 2, 1, 4);
	//Get the size of arr
	$size = count($arr1);
	echo "\n Before Sort :\n";
	$obj->display($arr1, $size);
	//Sort element
	$obj->sort_element($arr1, $size);
	echo "\n After Sort :\n";
	$obj->display($arr1, $size);
	//Given array have 2^4 elements
	$arr2 = array(8, 2, 9, -6, 3, 2, 31, 41, 2, 1, 67, 32, 24, 21, 4, 5);
	//Get the size of arr
	$size = count($arr2);
	echo "\n Before Sort :\n";
	$obj->display($arr2, $size);
	//Sort element
	$obj->sort_element($arr2, $size);
	echo "\n After Sort :\n";
	$obj->display($arr2, $size);
}
main();

Output

 Before Sort :
 3 6 2 5 -7 2 1 4

 After Sort :
 -7 1 2 2 3 4 5 6

 Before Sort :
 8 2 9 -6 3 2 31 41 2 1 67 32 24 21 4 5

 After Sort :
 -6 1 2 2 2 3 4 5 8 9 21 24 31 32 41 67
// Node Js Program 
// Sort array elements by using bitonic sort
// Given program are perfectly work when given input array size have equal to power of 2
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");
	}
	merge_element(arr, low, high, order)
	{
		if (high > 1)
		{
			var position = parseInt(high / 2);
			var temp = 0;
			var j = 0;
			//Loop controlling variable
			var i = 0;
			for (i = low; i < low + position; i++)
			{
				j = i + position;
				if ((order == 1 && arr[i] > arr[j]) || (order == 0 && arr[i] < arr[j]))
				{
					//Interchange the elements
					temp = arr[i];
					arr[i] = arr[j];
					arr[j] = temp;
				}
			}
			this.merge_element(arr, low, position, order);
			this.merge_element(arr, low + position, position, order);
		}
	}
	//produce bitonic sequence and sorted combine its elements
	bitonic_sort(arr, low, high, order)
	{
		if (high > 1)
		{
			var position = parseInt(high / 2);
			// sort element in ascending order 
			this.bitonic_sort(arr, low, position, 1);
			// sort element in descending order
			this.bitonic_sort(arr, low + position, position, 0);
			// merge equence in ascending order 
			this.merge_element(arr, low, high, order);
		}
	}
	sort_element(arr, size)
	{
		this.bitonic_sort(arr, 0, size, 1);
	}
}

function main()
{
	var obj = new MySort();
	//Define an array of integers
	var arr1 = [3, 6, 2, 5, -7, 2, 1, 4];
	//Get the size of arr
	var size = arr1.length;
	process.stdout.write("\n Before Sort :\n");
	obj.display(arr1, size);
	//Sort element
	obj.sort_element(arr1, size);
	process.stdout.write("\n After Sort :\n");
	obj.display(arr1, size);
	//Given array have 2^4 elements
	var arr2 = [8, 2, 9, -6, 3, 2, 31, 41, 2, 1, 67, 32, 24, 21, 4, 5];
	//Get the size of arr
	size = arr2.length;
	process.stdout.write("\n Before Sort :\n");
	obj.display(arr2, size);
	//Sort element
	obj.sort_element(arr2, size);
	process.stdout.write("\n After Sort :\n");
	obj.display(arr2, size);
}
main();

Output

 Before Sort :
 3 6 2 5 -7 2 1 4

 After Sort :
 -7 1 2 2 3 4 5 6

 Before Sort :
 8 2 9 -6 3 2 31 41 2 1 67 32 24 21 4 5

 After Sort :
 -6 1 2 2 2 3 4 5 8 9 21 24 31 32 41 67
#  Python 3 Program 
#  Sort array elements by using bitonic sort
#  Given program are perfectly work when given input array size have equal to power of 2
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 = "")
	
	def merge_element(self, arr, low, high, order) :
		if (high > 1) :
			position = int(high / 2)
			temp = 0
			j = 0
			# Loop controlling variable
			i = low
			while (i < low + position) :
				j = i + position
				if ((order == 1 and arr[i] > arr[j]) or(order == 0 and arr[i] < arr[j])) :
					# Interchange the elements
					temp = arr[i]
					arr[i] = arr[j]
					arr[j] = temp
				
				i += 1
			
			self.merge_element(arr, low, position, order)
			self.merge_element(arr, low + position, position, order)
		
	
	# produce bitonic sequence and sorted combine its elements
	def bitonic_sort(self, arr, low, high, order) :
		if (high > 1) :
			position = int(high / 2)
			#  sort element in ascending order 
			self.bitonic_sort(arr, low, position, 1)
			#  sort element in descending order
			self.bitonic_sort(arr, low + position, position, 0)
			#  merge equence in ascending order 
			self.merge_element(arr, low, high, order)
		
	
	def sort_element(self, arr, size) :
		self.bitonic_sort(arr, 0, size, 1)
	

def main() :
	obj = MySort()
	# Define an array of integers
	arr1 = [3, 6, 2, 5, -7, 2, 1, 4]
	# Get the size of arr
	size = len(arr1)
	print("\n Before Sort :\n", end = "")
	obj.display(arr1, size)
	# Sort element
	obj.sort_element(arr1, size)
	print("\n After Sort :\n", end = "")
	obj.display(arr1, size)
	# Given array have 2^4 elements
	arr2 = [8, 2, 9, -6, 3, 2, 31, 41, 2, 1, 67, 32, 24, 21, 4, 5]
	# Get the size of arr
	size = len(arr2)
	print("\n Before Sort :\n", end = "")
	obj.display(arr2, size)
	# Sort element
	obj.sort_element(arr2, size)
	print("\n After Sort :\n", end = "")
	obj.display(arr2, size)

if __name__ == "__main__": main()

Output

 Before Sort :
  3  6  2  5  -7  2  1  4

 After Sort :
  -7  1  2  2  3  4  5  6

 Before Sort :
  8  2  9  -6  3  2  31  41  2  1  67  32  24  21  4  5

 After Sort :
  -6  1  2  2  2  3  4  5  8  9  21  24  31  32  41  67
#  Ruby Program 
#  Sort array elements by using bitonic sort
#  Given program are perfectly work when given input array size have equal to power of 2
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
	def merge_element(arr, low, high, order)
	
		if (high > 1)
		
			position = high / 2
			temp = 0
			j = 0
			# Loop controlling variable
			i = low
			while (i < low + position)
			
				j = i + position
				if ((order == 1 && arr[i] > arr[j]) || (order == 0 && arr[i] < arr[j]))
				
					# Interchange the elements
					temp = arr[i]
					arr[i] = arr[j]
					arr[j] = temp
				end
				i += 1
			end
			self.merge_element(arr, low, position, order)
			self.merge_element(arr, low + position, position, order)
		end
	end
	# produce bitonic sequence and sorted combine its elements
	def bitonic_sort(arr, low, high, order)
	
		if (high > 1)
		
			position = high / 2
			#  sort element in ascending order 
			self.bitonic_sort(arr, low, position, 1)
			#  sort element in descending order
			self.bitonic_sort(arr, low + position, position, 0)
			#  merge equence in ascending order 
			self.merge_element(arr, low, high, order)
		end
	end
	def sort_element(arr, size)
	
		self.bitonic_sort(arr, 0, size, 1)
	end
end
def main()

	obj = MySort.new()
	# Define an array of integers
	arr1 = [3, 6, 2, 5, -7, 2, 1, 4]
	# Get the size of arr
	size = arr1.length
	print("\n Before Sort :\n")
	obj.display(arr1, size)
	# Sort element
	obj.sort_element(arr1, size)
	print("\n After Sort :\n")
	obj.display(arr1, size)
	# Given array have 2^4 elements
	arr2 = [8, 2, 9, -6, 3, 2, 31, 41, 2, 1, 67, 32, 24, 21, 4, 5]
	# Get the size of arr
	size = arr2.length
	print("\n Before Sort :\n")
	obj.display(arr2, size)
	# Sort element
	obj.sort_element(arr2, size)
	print("\n After Sort :\n")
	obj.display(arr2, size)
end
main()

Output

 Before Sort :
 3 6 2 5 -7 2 1 4

 After Sort :
 -7 1 2 2 3 4 5 6

 Before Sort :
 8 2 9 -6 3 2 31 41 2 1 67 32 24 21 4 5

 After Sort :
 -6 1 2 2 2 3 4 5 8 9 21 24 31 32 41 67

// Scala Program 
// Sort array elements by using bitonic sort
// Given program are perfectly work when given input array size have equal to power of 2
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");
	}
	def merge_element(arr: Array[Int], low: Int, high: Int, order: Int): Unit = {
		if (high > 1)
		{
			var position: Int = (high / 2).toInt;
			var temp: Int = 0;
			var j: Int = 0;
			//Loop controlling variable
			var i: Int = low;
			while (i < low + position)
			{
				j = i + position;
				if ((order == 1 && arr(i) > arr(j)) || (order == 0 && arr(i) < arr(j)))
				{
					//Interchange the elements
					temp = arr(i);
					arr(i) = arr(j);
					arr(j) = temp;
				}
				i += 1;
			}
			merge_element(arr, low, position, order);
			merge_element(arr, low + position, position, order);
		}
	}
	//produce bitonic sequence and sorted combine its elements
	def bitonic_sort(arr: Array[Int], low: Int, high: Int, order: Int): Unit = {
		if (high > 1)
		{
			var position: Int = (high / 2).toInt;
			// sort element in ascending order 
			bitonic_sort(arr, low, position, 1);
			// sort element in descending order
			bitonic_sort(arr, low + position, position, 0);
			// merge equence in ascending order 
			merge_element(arr, low, high, order);
		}
	}
	def sort_element(arr: Array[Int], size: Int): Unit = {
		bitonic_sort(arr, 0, size, 1);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: MySort = new MySort();
		//Define an array of integers
		var arr1: Array[Int] = Array(3, 6, 2, 5, -7, 2, 1, 4);
		//Get the size of arr
		var size: Int = arr1.length;
		print("\n Before Sort :\n");
		obj.display(arr1, size);
		//Sort element
		obj.sort_element(arr1, size);
		print("\n After Sort :\n");
		obj.display(arr1, size);
		//Given array have 2^4 elements
		var arr2: Array[Int] = Array(8, 2, 9, -6, 3, 2, 31, 41, 2, 1, 67, 32, 24, 21, 4, 5);
		//Get the size of arr
		size = arr2.length;
		print("\n Before Sort :\n");
		obj.display(arr2, size);
		//Sort element
		obj.sort_element(arr2, size);
		print("\n After Sort :\n");
		obj.display(arr2, size);
	}
}

Output

 Before Sort :
 3 6 2 5 -7 2 1 4

 After Sort :
 -7 1 2 2 3 4 5 6

 Before Sort :
 8 2 9 -6 3 2 31 41 2 1 67 32 24 21 4 5

 After Sort :
 -6 1 2 2 2 3 4 5 8 9 21 24 31 32 41 67
// Swift Program 
// Sort array elements by using bitonic sort
// Given program are perfectly work when given input array size have equal to power of 2
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("\n", terminator: "");
	}
	func merge_element(_ arr: inout[Int], _ low: Int, _ high: Int, _ order: Int)
	{
		if (high > 1)
		{
			let position: Int = high / 2;
			var temp: Int = 0;
			var j: Int = 0;
			//Loop controlling variable
			var i: Int = low;
			while (i < low + position)
			{
				j = i + position;
				if ((order == 1 && arr[i] > arr[j]) || (order == 0 && arr[i] < arr[j]))
				{
					//Interchange the elements
					temp = arr[i];
					arr[i] = arr[j];
					arr[j] = temp;
				}
				i += 1;
			}
			self.merge_element(&arr, low, position, order);
			self.merge_element(&arr, low + position, position, order);
		}
	}
	//produce bitonic sequence and sorted combine its elements
	func bitonic_sort(_ arr: inout[Int], _ low: Int, _ high: Int, _ order: Int)
	{
		if (high > 1)
		{
			let position: Int = high / 2;
			// sort element in ascending order 
			self.bitonic_sort(&arr, low, position, 1);
			// sort element in descending order
			self.bitonic_sort(&arr, low + position, position, 0);
			// merge equence in ascending order 
			self.merge_element(&arr, low, high, order);
		}
	}
	func sort_element(_ arr: inout[Int], _ size: Int)
	{
		self.bitonic_sort(&arr, 0, size, 1);
	}
}
func main()
{
	let obj: MySort = MySort();
	//Define an array of integers
	var arr1: [Int] = [3, 6, 2, 5, -7, 2, 1, 4];
	//Get the size of arr
	var size: Int = arr1.count;
	print("\n Before Sort :\n", terminator: "");
	obj.display(arr1, size);
	//Sort element
	obj.sort_element(&arr1, size);
	print("\n After Sort :\n", terminator: "");
	obj.display(arr1, size);
	//Given array have 2^4 elements
	var arr2: [Int] = [8, 2, 9, -6, 3, 2, 31, 41, 2, 1, 67, 32, 24, 21, 4, 5];
	//Get the size of arr
	size = arr2.count;
	print("\n Before Sort :\n", terminator: "");
	obj.display(arr2, size);
	//Sort element
	obj.sort_element(&arr2, size);
	print("\n After Sort :\n", terminator: "");
	obj.display(arr2, size);
}
main();

Output

 Before Sort :
  3  6  2  5  -7  2  1  4

 After Sort :
  -7  1  2  2  3  4  5  6

 Before Sort :
  8  2  9  -6  3  2  31  41  2  1  67  32  24  21  4  5

 After Sort :
  -6  1  2  2  2  3  4  5  8  9  21  24  31  32  41  67
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