Merge Sort

 Let's begin!

We've learned that Merge Sort is a sorting algorithm which follows the principle of Divide and Conquer and it have average time complexity as n(log n).

I have used two functions to implement Merge Sort:

1. Merge Sort (To Produce Sub Array)

• It will divide array in two parts form left to mid and mid+1 to end.
• It will produce sub array until it's a single element.

2. Merge (To Merge Sorted Array)

• It will sort the array by comparing elements in left array and right array and store it into temporary array.
• It will save the remaining value.
• It will copy the temporary array into main array

	//C++ Code
	#include <iostream>
	using std::endl;
	using std::cin;
	using std::cout;
	void display(int arr[], int length)
	{
	for(int i=0; i<length; i++)
	{
	cout<<arr[i]<<" ";
	}
	cout<<endl;
	}
	void merge(int arr[], int start, int mid, int end)
	{
	int length = end - start + 1;
	int temp[length];
	int index = 0, left = start, right = mid+1;
	while(left<=mid and right<=end)
	{
	if(arr[left] <= arr[right])
	{
	temp[index++] = arr[left++];
	}
	else
	{
	temp[index++] = arr[right++];
	}
	}
	while(left<=mid)
	{
	temp[index++] = arr[left++];
	}
	while(right<=end)
	{
	temp[index++] = arr[right++];
	}
	for(int i=start; i<=end; i++)
	{
	arr[i] = temp[i-start];
	}
	}
	void mergeSort(int arr[], int start, int end)
	{
	if (start<end)
	{
	int mid = (start+end)/2;
	mergeSort(arr, start, mid);
	mergeSort(arr, mid+1, end);
	merge(arr, start, mid, end);
	}
	}
	int main()
	{
	int length;
	cout<<"Length of the Array: ";
	cin>>length;
	int arr[length];
	for(int i=0; i<length; i++)
	{
	cout<<"Enter Element "<<(i+1)<<" : ";
	cin>>arr[i];
	}
	cout<<"Given Array: ";
	display(arr, length);
	mergeSort(arr, 0, length-1);
	cout<<"Sorted Array: ";
	display(arr, length);
	return 0;
	}

view raw merge_sort.cpp hosted with ❤ by GitHub

	package Algorithms.Sort;
	import java.util.Scanner;
	public class MergeSort {
	public static void display(int arr[], int length)
	{
	for(int i=0; i<length; i++)
	{
	System.out.print(arr[i] + " ");
	}
	System.out.println("");
	}
	public static void merge(int arr[], int start, int mid, int end)
	{
	int length = end - start + 1;
	int temp[] = new int[length];
	int index = 0, left = start, right = mid+1;
	while(left<=mid && right<=end)
	{
	if(arr[left] <= arr[right])
	{
	temp[index++] = arr[left++];
	}
	else
	{
	temp[index++] = arr[right++];
	}
	}
	while(left<=mid)
	{
	temp[index++] = arr[left++];
	}
	while(right<=end)
	{
	temp[index++] = arr[right++];
	}
	for(int i=start; i<=end; i++)
	{
	arr[i] = temp[i-start];
	}
	}
	public static void mergeSort(int arr[], int start, int end)
	{
	if(start<end)
	{
	int mid = (start+end)/2;
	mergeSort(arr, start, mid);
	mergeSort(arr, mid+1, end);
	merge(arr, start, mid, end);
	}
	}
	public static void main(String arg[])
	{
	Scanner scan = new Scanner(System.in);
	System.out.print("Enter length of the Array: ");
	int length = scan.nextInt();
	int arr [] = new int [length];
	for(int i=0; i<length; i++)
	{
	System.out.print("Enter Element "+(i+1)+" : ");
	arr[i] = scan.nextInt();
	}
	scan.close();
	System.out.print("Given Array: ");
	display(arr, length);
	mergeSort(arr, 0, length-1);
	System.out.print("Sorted Array: ");
	display(arr, length);
	}
	}

view raw MergeSort.java hosted with ❤ by GitHub

	def merge(arr, start, mid, end):
	temp = []
	left = start; right = mid+1
	while(left<=mid and right <=end):
	if arr[left] < arr[right]:
	temp.append(arr[left])
	left+=1
	else:
	temp.append(arr[right])
	right+=1
	while(left<=mid):
	temp.append(arr[left])
	left+=1
	while(right<=end):
	temp.append(arr[right])
	right+=1
	for i in range(start, end+1):
	arr[i] = temp[i - start]
	def mergeSort(arr, start, end):
	if start < end:
	mid = (start+end)//2
	mergeSort(arr, start, mid)
	mergeSort(arr, mid+1, end)
	merge(arr, start, mid, end)
	if __name__ == "__main__":
	user_input = input("Enter Length of the List: ")
	length = int(user_input)
	arr = []
	for num in range(length):
	user_input = input("Enter Element {} : ".format(num+1))
	arr.append(int(user_input))
	print("Given List: ", arr)
	mergeSort(arr, 0, length-1)
	print("Sorted Array: ",arr)

view raw merge_sort.py hosted with ❤ by GitHub