Skip to main content

Merge sort

Merge sort is a popular sorting algorithm that uses a divide-and-conquer approach to sort a list or an array. It was first introduced by John von Neumann in 1945.

The merge sort algorithm works by dividing the input array or list into two halves, sorting each half recursively using the same algorithm, and then merging the two sorted halves to produce a sorted output. The merging process involves comparing the elements of the two sorted halves and placing them in the correct order in a new, sorted array or list.

The algorithm has a time complexity of O(n log n), which makes it efficient for sorting large lists or arrays. It is also a stable sorting algorithm, meaning that it preserves the relative order of equal elements in the input.

In summary, merge sort can be described as follows:

  1. Divide the input array or list into two halves.
  2. Sort each half recursively using the merge sort algorithm.
  3. Merge the two sorted halves into a new, sorted array or list.
  4. Return the sorted array or list as output.

Here given code implementation process.

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

//Function which is display array elements
void display(int arr[], int size)
{
	for (int i = 0; i < size; ++i)
	{
		printf("  %d", arr[i]);
	}
	printf("\n");
}
//Sorted merge of given two subarrays of an array
void merge_elements(int arr[], int front, int tail, int middle)
{
	//Get the size of first subarray
	int s1 = (middle - front) + 1;
	//Get the size of second subarray
	int s2 = tail - middle;
	//Creating auxiliary storage to store elements
	int first_subarray[s1];
	int second_subarray[s2];
	//Loop controlling variables
	int i = 0;
	int j = 0;
	int counter = 0;
	//Get the elements of first subarray
	for (i = 0; i < s1; i++)
	{
		first_subarray[i] = arr[front + i];
	}
	//Get the elements of second subarray
	for (i = 0; i < s2; i++)
	{
		second_subarray[i] = arr[middle + i + 1];
	}
	i = 0;
	// Add sorted elements into actual array
	while (counter < s1 + s2)
	{
		//Check that both sub array element exists or not
		if (i < s1 && j < s2)
		{
			if (first_subarray[i] <= second_subarray[j])
			{
				//When first array [i] element are smaller 
				arr[front + counter] = first_subarray[i];
				i++;
			}
			else
			{
				//When second array [j] element are smaller 
				arr[front + counter] = second_subarray[j];
				j++;
			}
		}
		else if (i < s1)
		{
			//When first sub array element exists
			arr[front + counter] = first_subarray[i];
			i++;
		}
		else
		{
			//When second sub array element exists
			arr[front + counter] = second_subarray[j];
			j++;
		}
		counter++;
	}
}
//Split the array elements into two parts
void sort_element(int arr[], int front, int tail)
{
	if (front < tail)
	{
		//Get middle location of given index
		int middle = (front + tail) / 2;
		//Split the array into two parts
		sort_element(arr, front, middle);
		sort_element(arr, middle + 1, tail);
		//Combine split array into sorted way
		merge_elements(arr, front, tail, middle);
	}
}
int main()
{
	//Define an array of integers
	int arr[] = {
		8,
		3,
		8,
		-3,
		1,
		9,
		23,
		2,
		4,
		0,
		5
	};
	//Get the size of array
	int size = sizeof(arr) / sizeof(arr[0]);
	//Before sort
	printf("\n Array  :");
	display(arr, size);
	//Sort element
	sort_element(arr, 0, size - 1);
	//After sort
	printf("\n Array  :");
	display(arr, size);
	return 0;
}

Output

 Array  :  8  3  8  -3  1  9  23  2  4  0  5

 Array  :  -3  0  1  2  3  4  5  8  8  9  23
/*
  Java Program
  Sort array elements by using merge sort
*/
class MySort
{
	//Function which is display array elements
	public void display(int[] arr, int size)
	{
		for (int i = 0; i < size; ++i)
		{
			System.out.print(" " + arr[i]);
		}
		System.out.print("\n");
	}
	//Sorted merge of given two subarrays of an array
	public void merge_elements(int[] arr, int front, int tail, int middle)
	{
		//Get the size of first subarray
		int s1 = (middle - front) + 1;
		//Get the size of second subarray
		int s2 = tail - middle;
		//Creating auxiliary storage to store elements
		int[] first_subarray = new int[s1];
		int[] second_subarray = new int[s2];
		//Loop controlling variables
		int i = 0;
		int j = 0;
		int counter = 0;
		//Get the elements of first subarray
		for (i = 0; i < s1; i++)
		{
			first_subarray[i] = arr[front + i];
		}
		//Get the elements of second subarray
		for (i = 0; i < s2; i++)
		{
			second_subarray[i] = arr[middle + i + 1];
		}
		i = 0;
		// Add sorted elements into actual array
		while (counter < s1 + s2)
		{
			//Check that both sub array element exists or not
			if (i < s1 && j < s2)
			{
				if (first_subarray[i] <= second_subarray[j])
				{
					//When first array [i] element are smaller 
					arr[front + counter] = first_subarray[i];
					i++;
				}
				else
				{
					//When second array [j] element are smaller 
					arr[front + counter] = second_subarray[j];
					j++;
				}
			}
			else if (i < s1)
			{
				//When first sub array element exists
				arr[front + counter] = first_subarray[i];
				i++;
			}
			else
			{
				//When second sub array element exists
				arr[front + counter] = second_subarray[j];
				j++;
			}
			counter++;
		}
	}
	//Split the array elements into two parts
	public void sort_element(int[] arr, int front, int tail)
	{
		if (front < tail)
		{
			//Get middle location of given index
			int middle = (front + tail) / 2;
			//Split the array into two parts
			sort_element(arr, front, middle);
			sort_element(arr, middle + 1, tail);
			//Combine split array into sorted way
			merge_elements(arr, front, tail, middle);
		}
	}
	public static void main(String[] args)
	{
		MySort obj = new MySort();
		//Define an array of integers
		int[] arr = {
			8,
			3,
			8,
			-3,
			1,
			9,
			23,
			2,
			4,
			0,
			5
		};
		//Get the size of array
		int size = arr.length;
		System.out.print("\n Before Sort :\n");
		obj.display(arr, size);
		//Sort element
		obj.sort_element(arr, 0, size - 1);
		System.out.print("\n After Sort :\n");
		obj.display(arr, size);
	}
}

Output

 Before Sort :
 8 3 8 -3 1 9 23 2 4 0 5

 After Sort :
 -3 0 1 2 3 4 5 8 8 9 23
//Include header file
#include <iostream>

using namespace std;
/*
  C++ Program
  Sort array elements by using merge sort
*/
class MySort
{
	public:
		//Function which is display array elements
		void display(int arr[], int size)
		{
			for (int i = 0; i < size; ++i)
			{
				cout << " " << arr[i];
			}
			cout << "\n";
		}
	//Sorted merge of given two subarrays of an array
	void merge_elements(int arr[], int front, int tail, int middle)
	{
		//Get the size of first subarray
		int s1 = (middle - front) + 1;
		//Get the size of second subarray
		int s2 = tail - middle;
		int first_subarray[s1];
		int second_subarray[s2];
		//Loop controlling variables
		int i = 0;
		int j = 0;
		int counter = 0;
		//Get the elements of first subarray
		for (i = 0; i < s1; i++)
		{
			first_subarray[i] = arr[front + i];
		}
		//Get the elements of second subarray
		for (i = 0; i < s2; i++)
		{
			second_subarray[i] = arr[middle + i + 1];
		}
		i = 0;
		// Add sorted elements into actual array
		while (counter < s1 + s2)
		{
			//Check that both sub array element exists or not
			if (i < s1 && j < s2)
			{
				if (first_subarray[i] <= second_subarray[j])
				{
					//When first array [i] element are smaller 
					arr[front + counter] = first_subarray[i];
					i++;
				}
				else
				{
					//When second array [j] element are smaller 
					arr[front + counter] = second_subarray[j];
					j++;
				}
			}
			else if (i < s1)
			{
				//When first sub array element exists
				arr[front + counter] = first_subarray[i];
				i++;
			}
			else
			{
				//When second sub array element exists
				arr[front + counter] = second_subarray[j];
				j++;
			}
			counter++;
		}
	}
	//Split the array elements into two parts
	void sort_element(int arr[], int front, int tail)
	{
		if (front < tail)
		{
			//Get middle location of given index
			int middle = (front + tail) / 2;
			//Split the array into two parts
			this->sort_element(arr, front, middle);
			this->sort_element(arr, middle + 1, tail);
			//Combine split array into sorted way
			this->merge_elements(arr, front, tail, middle);
		}
	}
};
int main()
{
	MySort obj = MySort();
	int arr[] = {
		8 , 3 , 8 , -3 , 1 , 9 , 23 , 2 , 4 , 0 , 5
	};
	//Get the size of array
	int size = sizeof(arr) / sizeof(arr[0]);
	cout << "\n Before Sort :\n";
	obj.display(arr, size);
	//Sort element
	obj.sort_element(arr, 0, size - 1);
	cout << "\n After Sort :\n";
	obj.display(arr, size);
	return 0;
}

Output

 Before Sort :
 8 3 8 -3 1 9 23 2 4 0 5

 After Sort :
 -3 0 1 2 3 4 5 8 8 9 23
//Include namespace system
using System;
/*
  C# Program
  Sort array elements by using merge sort
*/
class MySort
{
	//Function which is display array elements
	public void display(int[] arr, int size)
	{
		for (int i = 0; i < size; ++i)
		{
			Console.Write(" " + arr[i]);
		}
		Console.Write("\n");
	}
	//Sorted merge of given two subarrays of an array
	public void merge_elements(int[] arr, int front, int tail, int middle)
	{
		//Get the size of first subarray
		int s1 = (middle - front) + 1;
		//Get the size of second subarray
		int s2 = tail - middle;
		int[] first_subarray = new int[s1];
		int[] second_subarray = new int[s2];
		//Loop controlling variables
		int i = 0;
		int j = 0;
		int counter = 0;
		//Get the elements of first subarray
		for (i = 0; i < s1; i++)
		{
			first_subarray[i] = arr[front + i];
		}
		//Get the elements of second subarray
		for (i = 0; i < s2; i++)
		{
			second_subarray[i] = arr[middle + i + 1];
		}
		i = 0;
		// Add sorted elements into actual array
		while (counter < s1 + s2)
		{
			//Check that both sub array element exists or not
			if (i < s1 && j < s2)
			{
				if (first_subarray[i] <= second_subarray[j])
				{
					//When first array [i] element are smaller 
					arr[front + counter] = first_subarray[i];
					i++;
				}
				else
				{
					//When second array [j] element are smaller 
					arr[front + counter] = second_subarray[j];
					j++;
				}
			}
			else if (i < s1)
			{
				//When first sub array element exists
				arr[front + counter] = first_subarray[i];
				i++;
			}
			else
			{
				//When second sub array element exists
				arr[front + counter] = second_subarray[j];
				j++;
			}
			counter++;
		}
	}
	//Split the array elements into two parts
	public void sort_element(int[] arr, int front, int tail)
	{
		if (front < tail)
		{
			//Get middle location of given index
			int middle = (front + tail) / 2;
			//Split the array into two parts
			sort_element(arr, front, middle);
			sort_element(arr, middle + 1, tail);
			//Combine split array into sorted way
			merge_elements(arr, front, tail, middle);
		}
	}
	public static void Main(String[] args)
	{
		MySort obj = new MySort();
		int[] arr = {
			8 , 3 , 8 , -3 , 1 , 9 , 23 , 2 , 4 , 0 , 5
		};
		//Get the size of array
		int size = arr.Length;
		Console.Write("\n Before Sort :\n");
		obj.display(arr, size);
		//Sort element
		obj.sort_element(arr, 0, size - 1);
		Console.Write("\n After Sort :\n");
		obj.display(arr, size);
	}
}

Output

 Before Sort :
 8 3 8 -3 1 9 23 2 4 0 5

 After Sort :
 -3 0 1 2 3 4 5 8 8 9 23
<?php
/*
  Php Program
  Sort array elements by using merge sort
*/
class MySort
{
	//Function which is display array elements
	public	function display( $arr, $size)
	{
		for ($i = 0; $i < $size; ++$i)
		{
			echo " ". $arr[$i];
		}
		echo "\n";
	}
	//Sorted merge of given two subarrays of an array
	public	function merge_elements( & $arr, $front, $tail, $middle)
	{
		//Get the size of first subarray
		$s1 = ($middle - $front) + 1;
		//Get the size of second subarray
		$s2 = $tail - $middle;
		//Creating auxiliary storage to store elements
		$first_subarray = array_fill(0, $s1, 0);
		$second_subarray = array_fill(0, $s2, 0);
		//Loop controlling variables
		$i = 0;
		$j = 0;
		$counter = 0;
		//Get the elements of first subarray
		for ($i = 0; $i < $s1; $i++)
		{
			$first_subarray[$i] = $arr[$front + $i];
		}
		//Get the elements of second subarray
		for ($i = 0; $i < $s2; $i++)
		{
			$second_subarray[$i] = $arr[$middle + $i + 1];
		}
		$i = 0;
		// Add sorted elements into actual array
		while ($counter < $s1 + $s2)
		{
			//Check that both sub array element exists or not
			if ($i < $s1 && $j < $s2)
			{
				if ($first_subarray[$i] <= $second_subarray[$j])
				{
					//When first array [i] element are smaller 
					$arr[$front + $counter] = $first_subarray[$i];
					$i++;
				}
				else
				{
					//When second array [j] element are smaller 
					$arr[$front + $counter] = $second_subarray[$j];
					$j++;
				}
			}
			else if ($i < $s1)
			{
				//When first sub array element exists
				$arr[$front + $counter] = $first_subarray[$i];
				$i++;
			}
			else
			{
				//When second sub array element exists
				$arr[$front + $counter] = $second_subarray[$j];
				$j++;
			}
			$counter++;
		}
	}
	//Split the array elements into two parts
	public	function sort_element( & $arr, $front, $tail)
	{
		if ($front < $tail)
		{
			//Get middle location of given index
			$middle = intval(($front + $tail) / 2);
			//Split the array into two parts
			$this->sort_element($arr, $front, $middle);
			$this->sort_element($arr, $middle + 1, $tail);
			//Combine split array into sorted way
			$this->merge_elements($arr, $front, $tail, $middle);
		}
	}
}

function main()
{
	$obj = new MySort();
	//Define an array of integers
	$arr = array(8, 3, 8, -3, 1, 9, 23, 2, 4, 0, 5);
	//Get the size of array
	$size = count($arr);
	echo "\n Before Sort :\n";
	$obj->display($arr, $size);
	//Sort element
	$obj->sort_element($arr, 0, $size - 1);
	echo "\n After Sort :\n";
	$obj->display($arr, $size);
}
main();

Output

 Before Sort :
 8 3 8 -3 1 9 23 2 4 0 5

 After Sort :
 -3 0 1 2 3 4 5 8 8 9 23
/*
  Node Js Program
  Sort array elements by using merge sort
*/
class MySort
{
	//Function which is display array elements
	display(arr, size)
	{
		for (var i = 0; i < size; ++i)
		{
			process.stdout.write(" " + arr[i]);
		}
		process.stdout.write("\n");
	}
	//Sorted merge of given two subarrays of an array
	merge_elements(arr, front, tail, middle)
	{
		//Get the size of first subarray
		var s1 = (middle - front) + 1;
		//Get the size of second subarray
		var s2 = tail - middle;
		//Creating auxiliary storage to store elements
		var first_subarray = Array(s1).fill(0);
		var second_subarray = Array(s2).fill(0);
		//Loop controlling variables
		var i = 0;
		var j = 0;
		var counter = 0;
		//Get the elements of first subarray
		for (i = 0; i < s1; i++)
		{
			first_subarray[i] = arr[front + i];
		}
		//Get the elements of second subarray
		for (i = 0; i < s2; i++)
		{
			second_subarray[i] = arr[middle + i + 1];
		}
		i = 0;
		// Add sorted elements into actual array
		while (counter < s1 + s2)
		{
			//Check that both sub array element exists or not
			if (i < s1 && j < s2)
			{
				if (first_subarray[i] <= second_subarray[j])
				{
					//When first array [i] element are smaller 
					arr[front + counter] = first_subarray[i];
					i++;
				}
				else
				{
					//When second array [j] element are smaller 
					arr[front + counter] = second_subarray[j];
					j++;
				}
			}
			else if (i < s1)
			{
				//When first sub array element exists
				arr[front + counter] = first_subarray[i];
				i++;
			}
			else
			{
				//When second sub array element exists
				arr[front + counter] = second_subarray[j];
				j++;
			}
			counter++;
		}
	}
	//Split the array elements into two parts
	sort_element(arr, front, tail)
	{
		if (front < tail)
		{
			//Get middle location of given index
			var middle = parseInt((front + tail) / 2);
			//Split the array into two parts
			this.sort_element(arr, front, middle);
			this.sort_element(arr, middle + 1, tail);
			//Combine split array into sorted way
			this.merge_elements(arr, front, tail, middle);
		}
	}
}

function main()
{
	var obj = new MySort();
	//Define an array of integers
	var arr = [8, 3, 8, -3, 1, 9, 23, 2, 4, 0, 5];
	//Get the size of array
	var size = arr.length;
	process.stdout.write("\n Before Sort :\n");
	obj.display(arr, size);
	//Sort element
	obj.sort_element(arr, 0, size - 1);
	process.stdout.write("\n After Sort :\n");
	obj.display(arr, size);
}
main();

Output

 Before Sort :
 8 3 8 -3 1 9 23 2 4 0 5

 After Sort :
 -3 0 1 2 3 4 5 8 8 9 23
#   Python 3 Program
#   Sort array elements by using merge sort

class MySort :
	# Function which is display array elements
	def display(self, arr, size) :
		i = 0
		while (i < size) :
			print(" ", arr[i], end = "")
			i += 1
		
		print("\n", end = "")
	
	# Sorted merge of given two subarrays of an array
	def merge_elements(self, arr, front, tail, middle) :
		# Get the size of first subarray
		s1 = (middle - front) + 1
		# Get the size of second subarray
		s2 = tail - middle
		# Creating auxiliary storage to store elements
		first_subarray = [0] * s1
		second_subarray = [0] * s2
		# Loop controlling variables
		i = 0
		j = 0
		counter = 0
		# Get the elements of first subarray
		i = 0
		while (i < s1) :
			first_subarray[i] = arr[front + i]
			i += 1
		
		# Get the elements of second subarray
		i = 0
		while (i < s2) :
			second_subarray[i] = arr[middle + i + 1]
			i += 1
		
		i = 0
		#  Add sorted elements into actual array
		while (counter < s1 + s2) :
			# Check that both sub array element exists or not
			if (i < s1 and j < s2) :
				if (first_subarray[i] <= second_subarray[j]) :
					# When first array [i] element are smaller 
					arr[front + counter] = first_subarray[i]
					i += 1
				else :
					# When second array [j] element are smaller 
					arr[front + counter] = second_subarray[j]
					j += 1
				
			
			elif(i < s1) :
				# When first sub array element exists
				arr[front + counter] = first_subarray[i]
				i += 1
			else :
				# When second sub array element exists
				arr[front + counter] = second_subarray[j]
				j += 1
			
			counter += 1
		
	
	# Split the array elements into two parts
	def sort_element(self, arr, front, tail) :
		if (front < tail) :
			# Get middle location of given index
			middle = int((front + tail) / 2)
			# Split the array into two parts
			self.sort_element(arr, front, middle)
			self.sort_element(arr, middle + 1, tail)
			# Combine split array into sorted way
			self.merge_elements(arr, front, tail, middle)
		
	

def main() :
	obj = MySort()
	# Define an array of integers
	arr = [8, 3, 8, -3, 1, 9, 23, 2, 4, 0, 5]
	# Get the size of array
	size = len(arr)
	print("\n Before Sort :\n", end = "")
	obj.display(arr, size)
	# Sort element
	obj.sort_element(arr, 0, size - 1)
	print("\n After Sort :\n", end = "")
	obj.display(arr, size)

if __name__ == "__main__": main()

Output

 Before Sort :
  8  3  8  -3  1  9  23  2  4  0  5

 After Sort :
  -3  0  1  2  3  4  5  8  8  9  23
#   Ruby Program
#   Sort array elements by using merge sort

class MySort

	# Function which is display array elements
	def display(arr, size)

		i = 0
		while (i < size)
		
			print(" ", arr[i])
			i += 1
		end
		print("\n")
	end
	# Sorted merge of given two subarrays of an array
	def merge_elements(arr, front, tail, middle)
	
		# Get the size of first subarray
		s1 = (middle - front) + 1
		# Get the size of second subarray
		s2 = tail - middle
		# Creating auxiliary storage to store elements
		first_subarray = Array.new(s1) {0}
		second_subarray = Array.new(s2) {0}
		# Loop controlling variables
		i = 0
		j = 0
		counter = 0
		# Get the elements of first subarray
		i = 0
		while (i < s1)
		
			first_subarray[i] = arr[front + i]
			i += 1
		end
		# Get the elements of second subarray
		i = 0
		while (i < s2)
		
			second_subarray[i] = arr[middle + i + 1]
			i += 1
		end
		i = 0
		#  Add sorted elements into actual array
		while (counter < s1 + s2)
		
			# Check that both sub array element exists or not
			if (i < s1 && j < s2)
			
				if (first_subarray[i] <= second_subarray[j])
				
					# When first array [i] element are smaller 
					arr[front + counter] = first_subarray[i]
					i += 1
				else
				
					# When second array [j] element are smaller 
					arr[front + counter] = second_subarray[j]
					j += 1
				end
			elsif(i < s1)
			
				# When first sub array element exists
				arr[front + counter] = first_subarray[i]
				i += 1
			else
			
				# When second sub array element exists
				arr[front + counter] = second_subarray[j]
				j += 1
			end
			counter += 1
		end
	end
	# Split the array elements into two parts
	def sort_element(arr, front, tail)
	
		if (front < tail)
		
			# Get middle location of given index
			middle = (front + tail) / 2
			# Split the array into two parts
			self.sort_element(arr, front, middle)
			self.sort_element(arr, middle + 1, tail)
			# Combine split array into sorted way
			self.merge_elements(arr, front, tail, middle)
		end
	end
end
def main()

	obj = MySort.new()
	# Define an array of integers
	arr = [8, 3, 8, -3, 1, 9, 23, 2, 4, 0, 5]
	# Get the size of array
	size = arr.length
	print("\n Before Sort :\n")
	obj.display(arr, size)
	# Sort element
	obj.sort_element(arr, 0, size - 1)
	print("\n After Sort :\n")
	obj.display(arr, size)
end
main()

Output

 Before Sort :
 8 3 8 -3 1 9 23 2 4 0 5

 After Sort :
 -3 0 1 2 3 4 5 8 8 9 23

/*
  Scala Program
  Sort array elements by using merge sort
*/
class MySort
{
	//Function which is display array elements
	def display(arr: Array[Int], size: Int): Unit = {
		var i: Int = 0;
		while (i < size)
		{
			print(" " + arr(i));
			i += 1;
		}
		print("\n");
	}
	//Sorted merge of given two subarrays of an array
	def merge_elements(arr: Array[Int], front: Int, tail: Int, middle: Int): Unit = {
		//Get the size of first subarray
		var s1: Int = (middle - front) + 1;
		//Get the size of second subarray
		var s2: Int = tail - middle;
		//Creating auxiliary storage to store elements
		var first_subarray: Array[Int] = Array.fill[Int](s1)(0);
		var second_subarray: Array[Int] = Array.fill[Int](s2)(0);
		//Loop controlling variables
		var i: Int = 0;
		var j: Int = 0;
		var counter: Int = 0;
		//Get the elements of first subarray
		i = 0;
		while (i < s1)
		{
			first_subarray(i) = arr(front + i);
			i += 1;
		}
		//Get the elements of second subarray
		i = 0;
		while (i < s2)
		{
			second_subarray(i) = arr(middle + i + 1);
			i += 1;
		}
		i = 0;
		// Add sorted elements into actual array
		while (counter < s1 + s2)
		{
			//Check that both sub array element exists or not
			if (i < s1 && j < s2)
			{
				if (first_subarray(i) <= second_subarray(j))
				{
					//When first array [i] element are smaller 
					arr(front + counter) = first_subarray(i);
					i += 1;
				}
				else
				{
					//When second array [j] element are smaller 
					arr(front + counter) = second_subarray(j);
					j += 1;
				}
			}
			else if (i < s1)
			{
				//When first sub array element exists
				arr(front + counter) = first_subarray(i);
				i += 1;
			}
			else
			{
				//When second sub array element exists
				arr(front + counter) = second_subarray(j);
				j += 1;
			}
			counter += 1;
		}
	}
	//Split the array elements into two parts
	def sort_element(arr: Array[Int], front: Int, tail: Int): Unit = {
		if (front < tail)
		{
			//Get middle location of given index
			var middle: Int = ((front + tail) / 2).toInt;
			//Split the array into two parts
			sort_element(arr, front, middle);
			sort_element(arr, middle + 1, tail);
			//Combine split array into sorted way
			merge_elements(arr, front, tail, middle);
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: MySort = new MySort();
		//Define an array of integers
		var arr: Array[Int] = Array(8, 3, 8, -3, 1, 9, 23, 2, 4, 0, 5);
		//Get the size of array
		var size: Int = arr.length;
		print("\n Before Sort :\n");
		obj.display(arr, size);
		//Sort element
		obj.sort_element(arr, 0, size - 1);
		print("\n After Sort :\n");
		obj.display(arr, size);
	}
}

Output

 Before Sort :
 8 3 8 -3 1 9 23 2 4 0 5

 After Sort :
 -3 0 1 2 3 4 5 8 8 9 23
/*
  Swift Program
  Sort array elements by using merge sort
*/
class MySort
{
	//Function which is display array elements
	func display(_ arr: [Int], _ size: Int)
	{
		var i: Int = 0;
		while (i < size)
		{
			print(" ", arr[i], terminator: "");
			i += 1;
		}
		print("\n", terminator: "");
	}
	//Sorted merge of given two subarrays of an array
	func merge_elements(_ arr: inout[Int], _ front: Int, _ tail: Int, _ middle: Int)
	{
		//Get the size of first subarray
		let s1: Int = (middle - front) + 1;
		//Get the size of second subarray
		let s2: Int = tail - middle;
		//Creating auxiliary storage to store elements
		var first_subarray: [Int] = Array(repeating: 0, count: s1);
		var second_subarray: [Int] = Array(repeating: 0, count: s2);
		//Loop controlling variables
		var i: Int = 0;
		var j: Int = 0;
		var counter: Int = 0;
		//Get the elements of first subarray
		i = 0;
		while (i < s1)
		{
			first_subarray[i] = arr[front + i];
			i += 1;
		}
		//Get the elements of second subarray
		i = 0;
		while (i < s2)
		{
			second_subarray[i] = arr[middle + i + 1];
			i += 1;
		}
		i = 0;
		// Add sorted elements into actual array
		while (counter < s1 + s2)
		{
			//Check that both sub array element exists or not
			if (i < s1 && j < s2)
			{
				if (first_subarray[i] <= second_subarray[j])
				{
					//When first array [i] element are smaller 
					arr[front + counter] = first_subarray[i];
					i += 1;
				}
				else
				{
					//When second array [j] element are smaller 
					arr[front + counter] = second_subarray[j];
					j += 1;
				}
			}
			else if (i < s1)
			{
				//When first sub array element exists
				arr[front + counter] = first_subarray[i];
				i += 1;
			}
			else
			{
				//When second sub array element exists
				arr[front + counter] = second_subarray[j];
				j += 1;
			}
			counter += 1;
		}
	}
	//Split the array elements into two parts
	func sort_element(_ arr: inout[Int], _ front: Int, _ tail: Int)
	{
		if (front < tail)
		{
			//Get middle location of given index
			let middle: Int = (front + tail) / 2;
			//Split the array into two parts
			self.sort_element(&arr, front, middle);
			self.sort_element(&arr, middle + 1, tail);
			//Combine split array into sorted way
			self.merge_elements(&arr, front, tail, middle);
		}
	}
}
func main()
{
	let obj: MySort = MySort();
	//Define an array of integers
	var arr: [Int] = [8, 3, 8, -3, 1, 9, 23, 2, 4, 0, 5];
	//Get the size of array
	let size: Int = arr.count;
	print("\n Before Sort :\n", terminator: "");
	obj.display(arr, size);
	//Sort element
	obj.sort_element(&arr, 0, size - 1);
	print("\n After Sort :\n", terminator: "");
	obj.display(arr, size);
}
main();

Output

 Before Sort :
  8  3  8  -3  1  9  23  2  4  0  5

 After Sort :
  -3  0  1  2  3  4  5  8  8  9  23
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