# Python Program - Merge Sort

Merge sort is a divide and conquer algorithm. It is based on the idea of dividing the unsorted array into several sub-array until each sub-array consists of a single element and merging those sub-array in such a way that results into a sorted array. The process step of merge sort can be summarized as follows:

**Divide:**Divide the unsorted array into several sub-array until each sub-array contains only single element.**Merge:**Merge the sub-arrays in such way that results into sorted array and merge until achieves the original array.**Merging technique:**the first element of the two sub-arrays is considered and compared. For ascending order sorting, the element with smaller value is taken from the sub-array and becomes a new element of the sorted array. This process is repeated until both sub-array are emptied and the merged array becomes sorted array.

### Example:

To understand the merge sort, lets consider an unsorted array *[4, 9, -4]* (right side array created after 11th process in the below diagram) and discuss each step taken to sort the array in ascending order.

At the first step, the array *[4, 9, -4]* is divided into two sub-array. The first sub-array contains *[4, 9]* and second sub-array contains *[-4]*. As the number of element in the first sub-array is greater than one, it is further divided into sub-arrays consisting of elements *[4]* and *[9]* respectively. As the number of elements in all sub-arrays is one, hence the further dividing of the array can not be done.

In the merging process, The sub-arrays formed in the last step are combined together using the process mentioned above to form a sorted array. First, *[4]* and *[9]* sub-arrays are merged together to form a sorted sub-array *[4, 9]*. Then *[4, 9]* and *[-4]* sub-arrays are merged together to form final sorted array *[-4, 4, 9]*

## Implementation of Merge Sort

public class MyClass { // function for merge sort - splits the array // and call merge function to sort and merge the array // mergesort is a recursive function static void mergesort(int Array[], int left, int right) { if (left < right) { int mid = left + (right - left)/2; mergesort(Array, left, mid); mergesort(Array, mid+1, right); merge(Array, left, mid, right); } } // merge function performs sort and merge operations // for mergesort function static void merge(int Array[], int left, int mid, int right) { // Create two temporary array to hold split // elements of main array int n1 = mid - left + 1; //no of elements in LeftArray int n2 = right - mid; //no of elements in RightArray int LeftArray[] = new int[n1]; int[] RightArray = new int [n2]; for(int i=0; i < n1; i++) { LeftArray[i] = Array[left + i]; } for(int i=0; i < n2; i++) { RightArray[i] = Array[mid + i + 1]; } // In below section x, y and z represents index number // of LeftArray, RightArray and Array respectively int x=0, y=0, z=left; while(x < n1 && y < n2) { if(LeftArray[x] < RightArray[y]) { Array[z] = LeftArray[x]; x++; } else { Array[z] = RightArray[y]; y++; } z++; } // Copying the remaining elements of LeftArray while(x < n1) { Array[z] = LeftArray[x]; x++; z++; } // Copying the remaining elements of RightArray while(y < n2) { Array[z] = RightArray[y]; y++; z++; } } // function to print array static void PrintArray(int Array[]) { int n = Array.length; for (int i=0; i<n; i++) System.out.print(Array[i] + " "); System.out.println(); } // test the code public static void main(String[] args) { int[] MyArray = {10, 1, 23, 50, 4, 9, -4}; int n = MyArray.length; System.out.println("Original Array"); PrintArray(MyArray); mergesort(MyArray, 0, n-1); System.out.println("\nSorted Array"); PrintArray(MyArray); } }

The above code will give the following output:

Original Array 10 1 23 50 4 9 -4 Sorted Array -4 1 4 9 10 23 50

### Time Complexity:

In all cases (worst, average and best), merge sort always divides the array until all sub-arrays contains single element and takes linear time to merge those sub-arrays. Dividing process has time complexity *Θ(logN)* and merging process has time complexity *Θ(N)*. Therefore, in all cases, the time complexity of merge sort is *Θ(NlogN)*.

### Recommended Pages

- Java Program - To Check Prime Number
- Java Program - Bubble Sort
- Java Program - Selection Sort
- Java Program - Maximum Subarray Sum
- Java Program - Reverse digits of a given Integer
- Java - Swap two numbers
- Java Program - Fibonacci Sequence
- Java Program - Insertion Sort
- Java Program - Find Factorial of a Number
- Java Program - Find HCF of Two Numbers
- Java Program - To Check Whether a Number is Palindrome or Not
- Java Program - To Check Whether a String is Palindrome or Not
- Java Program - Heap Sort
- Java Program - Quick Sort
- Java - Swap Two Numbers without using Temporary Variable
- Java Program - To Check Armstrong Number
- Java Program - Counting Sort
- Java Program - Radix Sort
- Java Program - Find Largest Number among Three Numbers
- Java Program - Print Floyd's Triangle