# Merge Sort Algorithm – Java, C, and Python Implementation

Merge sort is one of the most efficient sorting algorithms. It works on the principle of Divide and Conquer based on the idea of breaking down a list into several sub-lists until each sublist consists of a single element and merging those sublists in a manner that results into a sorted list.

## Merge Sort Working Rule

The concept of Divide and Conquer involves three steps:

1. Divide the problem into multiple subproblems.
2. Solve the Sub Problems. The idea is to break down the problem into atomic subproblems, where they are actually solved.
3. Combine the solutions of the subproblems to find the solution of the actual problem.

So, the merge sort working rule involves the following steps:

1. Divide the unsorted array into subarray, each containing a single element.
2. Take adjacent pairs of two single-element array and merge them to form an array of 2 elements.
3. Repeat the process till a single sorted array is obtained.

An array of Size ‘N’ is divided into two parts ‘N/2’ size of each. then those arrays are further divided till we reach a single element.

The base case here is reaching one single element. When the base case is hit, we start merging the left part and the right part and we get a sorted array at the end.

Merge sort repeatedly breaks down an array into several subarrays until each subarray consists of a single element and merging those subarrays in a manner that results in a sorted array.

### Merge Sort Algorithm Flow

Array = {70,50,30,10,20,40,60} MergeSort

We repeatedly break down the array in two parts, the left part, and the right part. the division takes place from the mid element.

We divide until we reach a single element and then we start combining them to form a Sorted Array.

## Merge Sort Implementations

We will implement the merge sort algorithm in Java, C, and Python.

### 1. Java Implementation

``````
package com.journaldev.ds;

public class MergeSort {

public static void main(String[] args) {

int[] arr = { 70, 50, 30, 10, 20, 40, 60 };

int[] merged = mergeSort(arr, 0, arr.length - 1);

for (int val : merged) {
System.out.print(val + " ");
}

}

public static int[] mergeTwoSortedArrays(int[] one, int[] two) {

int[] sorted = new int[one.length + two.length];

int i = 0;
int j = 0;
int k = 0;

while (i < one.length && j < two.length) {

if (one[i] < two[j]) {
sorted[k] = one[i];
k++;
i++;
} else {
sorted[k] = two[j];
k++;
j++;
}
}

if (i == one.length) {

while (j < two.length) {
sorted[k] = two[j];
k++;
j++;
}
}

if (j == two.length) {

while (i < one.length) {
sorted[k] = one[i];
k++;
i++;
}
}

return sorted;

}

public static int[] mergeSort(int[] arr, int lo, int hi) {

if (lo == hi) {
int[] br = new int;
br = arr[lo];

return br;
}

int mid = (lo + hi) / 2;

int[] fh = mergeSort(arr, lo, mid);
int[] sh = mergeSort(arr, mid + 1, hi);

int[] merged = mergeTwoSortedArrays(fh, sh);

return merged;
}

}
``````

OUTPUT Merge Sort Algorithm Java Implementation

### 2. C Implementation

``````
#include <stdio.h>

void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 =  r - m;

/* create temp arrays */
int L[n1], R[n2];

/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];

/* Merge the temp arrays back into arr[l..r]*/
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}

/* Copy the remaining elements of L[], if there
are any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}

/* Copy the remaining elements of R[], if there
are any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}

/* l is for left index and r is the right index of the
sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
if (l < r)
{
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l+(r-l)/2;

// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);

merge(arr, l, m, r);
}
}

void printArray(int A[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}

/* Driver program to test above functions */
int main()
{
int arr[] = {70, 50, 30, 10, 20, 40,60};
int arr_size = sizeof(arr)/sizeof(arr);

printf("Given array is \n");
printArray(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

printf("\nSorted array is \n");
printArray(arr, arr_size);
return 0;
}
``````

OUTPUT Merge Sort C Implementation

### 3. Python Implementation

``````
def merge_sort(unsorted_array):
if len(unsorted_array) > 1:
mid = len(unsorted_array) // 2  # Finding the mid of the array
left = unsorted_array[:mid]  # Dividing the array elements
right = unsorted_array[mid:]  # into 2 halves

merge_sort(left)
merge_sort(right)

i = j = k = 0

#  data to temp arrays L[] and R[]
while i < len(left) and j < len(right):
if left[i] < right[j]:
unsorted_array[k] = left[i]
i += 1
else:
unsorted_array[k] = right[j]
j += 1
k += 1

# Checking if any element was left
while i < len(left):
unsorted_array[k] = left[i]
i += 1
k += 1

while j < len(right):
unsorted_array[k] = right[j]
j += 1
k += 1

# Code to print the list
def print_list(array1):
for i in range(len(array1)):
print(array1[i], end=" ")
print()

# driver code to test the above code
if __name__ == '__main__':
array = [12, 11, 13, 5, 6, 7]
print("Given array is", end="\n")
print_list(array)
merge_sort(array)
print("Sorted array is: ", end="\n")
print_list(array)
``````

OUTPUT Merge Sort Python Code

## Merge Sort Time and Space Complexity

### 1. Space Complexity

Auxiliary Space: O(n)
Sorting In Place: No
Algorithm : Divide and Conquer

### 2. Time Complexity

Merge Sort is a recursive algorithm and time complexity can be expressed as following recurrence relation.

T(n) = 2T(n/2) + O(n)

The solution of the above recurrence is O(nLogn). The list of size N is divided into a max of Logn parts, and the merging of all sublists into a single list takes O(N) time, the worst-case run time of this algorithm is O(nLogn)

Best Case Time Complexity: O(n*log n)

Worst Case Time Complexity: O(n*log n)

Average Time Complexity: O(n*log n)

The time complexity of MergeSort is O(n*Log n) in all the 3 cases (worst, average and best) as the mergesort always divides the array into two halves and takes linear time to merge two halves.