### Merge Sort

#### sorting algorithm merge sort algorithm

The merge sort is a comparison-based sorting algorithm based on divide and conquer strategy. It has a usual performance of Θ(nlogn).

This algorithm works by dividing the unsorted list into n sublists; each one containing one element (which is considered sorted, since it only has one element).

Then it merges the sublists to produce new sorted sublists, this is repeated until there's only one sublist remaining, which is the resulting sorted list.

### Complexity

• Worst case time complexity: Θ(N log N)
• Average case time complexity: Θ(N log N)
• Best case time complexity: Θ(N log N) (naive); Θ(N) (natural variant)
• Space complexity: Θ(N) (auxillary); Θ(1) (using linked lists).

### Implementation

Implementation of Merge Sort algorithm in 5 languages that includes C, C++, Java, Python and C#.

• C
• C++
• Java
• Python
• C#

### C


/*
* Part of Cosmos by OpenGenus Foundation
*/
#include <stdio.h>
#define max 10
int a[11] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0 };
int b[10];
void merging(int low, int mid, int high) {
int l1, l2, i;
for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) {
if(a[l1] <= a[l2])
b[i] = a[l1++];
else
b[i] = a[l2++];
}
while(l1 <= mid)
b[i++] = a[l1++];
while(l2 <= high)
b[i++] = a[l2++];
for(i = low; i <= high; i++)
a[i] = b[i];
}
void sort(int low, int high) {
int mid;
if(low < high) {
mid = (low + high) / 2;
sort(low, mid);
sort(mid+1, high);
merging(low, mid, high);
} else {
return;
}
}
int main() {
int i;
printf("List before sorting\n");
for(i = 0; i <= max; i++)
printf("%d ", a[i]);
sort(0, max);
printf("\nList after sorting\n");
for(i = 0; i <= max; i++)
printf("%d ", a[i]);
}


### C++


/*
Part of Cosmos by OpenGenus Foundation
merge sort synopsis
namespace merge_sort_impl {
template<typename _Random_Acccess_Iter>
_Random_Acccess_Iter
}
template<typename _Random_Acccess_Iter, typename _Compare>
void mergeSort(_Random_Acccess_Iter begin, _Random_Acccess_Iter end, _Compare comp);
template<typename _Random_Acccess_Iter>
void mergeSort(_Random_Acccess_Iter begin, _Random_Acccess_Iter end);
*/
#include <list>
#include <iterator>
#include <cstddef>
namespace merge_sort_impl {
template<typename _Random_Acccess_Iter>
_Random_Acccess_Iter
{
return it;
}
template<typename _Random_Acccess_Iter, typename _Compare>
void merge(_Random_Acccess_Iter begin,
_Random_Acccess_Iter end,
_Compare comp)
{
using value_type = typename std::iterator_traits<_Random_Acccess_Iter>::value_type;
auto end1 = begin;
auto begin1 = begin,
begin2 = end1,
end2 = end;
std::list<value_type> tmp{};
while (begin1 < end1 &&  begin2 < end2)
tmp.push_back(comp(*begin1, *begin2) ? *begin1++ : *begin2++);
while (begin1 < end1)
*--begin2 = *--end1;
while (!tmp.empty())
{
*--begin2 = tmp.back();
tmp.pop_back();
}
}
}
template<typename _Random_Acccess_Iter, typename _Compare>
void
mergeSort(_Random_Acccess_Iter begin, _Random_Acccess_Iter end, _Compare comp)
{
size_t dist = std::distance(begin, end);
if (dist > 1)
{
auto mid = begin;
mergeSort(begin, mid, comp);
mergeSort(mid, end, comp);
merge_sort_impl::merge(begin, end, comp);
}
}
template<typename _Random_Acccess_Iter>
void
mergeSort(_Random_Acccess_Iter begin, _Random_Acccess_Iter end)
{
using value_type = typename std::iterator_traits<_Random_Acccess_Iter>::value_type;
mergeSort(begin, end, std::less<value_type>());
}


### Java


/* Java program for Merge Sort */
// Part of Cosmos by OpenGenus Foundation
class MergeSort {
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
private void merge(int arr[], int l, int m, int r) {
// Find sizes of two subarrays to be merged
int n1 = m - l + 1;
int n2 = r - m;
/* Create temp arrays */
int L[] = new int [n1];
int R[] = new int [n2];
/*Copy data to temp arrays*/
System.arraycopy(arr, l + 0, L, 0, n1);
for (int j=0; j<n2; ++j)
R[j] = arr[m + 1+ j];
/* Merge the temp arrays */
// Initial indexes of first and second subarrays
int i = 0, j = 0;
// Initial index of merged subarry array
int k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
/* Copy remaining elements of L[] if any */
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
/* Copy remaining elements of R[] if any */
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// Main function that sorts arr[l..r] using
// merge()
private void sort(int arr[], int l, int r) {
if (l < r) {
// Find the middle point
int m = (l+r)/2;
// Sort first and second halves
sort(arr, l, m);
sort(arr , m+1, r);
// Merge the sorted halves
merge(arr, l, m, r);
}
}
/* A utility function to print array of size n */
private static void printArray(int arr[]) {
int n = arr.length;
for (int anArr : arr) System.out.print(anArr + " ");
System.out.println();
}
// Driver method
public static void main(String args[]) {
int arr[] = {12, 11, 13, 5, 6, 7};
System.out.println("Given Array");
printArray(arr);
MergeSort ob = new MergeSort();
ob.sort(arr, 0, arr.length-1);
System.out.println("\nSorted array");
printArray(arr);
}
}


### Python


# Part of Cosmos by OpenGenus Foundation
# Split array in half, sort the 2 halves and merge them.
# When merging we pick the smallest element in the array.
# The "edge" case is when one of the arrays has no elements in it
# To avoid checking and breaking the look, finding which array has elements and then
# Starting another loop, we simply alias the arrays. This abstracts the issue without
# Creating a mess of code. When we alias, we decide with Xor which array to pick,
# Since we cover 0 ^ 0 case in the beginning of the loop,
# while bool(a) or bool(b) makes 0^0 is impossible to happen, Xor has 3 cases, 1 ^ 0, 0 ^ 1, 1^1 to evaluate.
# Since the 2 first cases are the edge we go inside the loop and alias the array that has elements in it.
# If it's 1^1 we simply pick the array with the smallest element.
from random import randint
def merge_sort(array):
if len(array) == 1:
return array
left = merge_sort(array[:(len(array)//2)])
right = merge_sort(array[(len(array)//2):])
out = []
while bool(left) or bool(right):
if bool(left) ^ bool(right):
alias = left if left else right
else:
alias = left if left[0] < right[0] else right
out.append(alias[0])
alias.remove(alias[0])
return out
randomized: list = [randint(0, 1000) for x in range(10000)]
clone = [x for x in randomized]
assert sorted(clone) == merge_sort(randomized)


### Go


package main
import (
"fmt"
)
func main() {
A := []int{3, 5, 1, 6, 1, 7, 2, 4, 5}
fmt.Println(sort(A))
}
// top-down approach
func sort(A []int) []int {
if len(A) <= 1 {
return A
}
left, right := split(A)
left = sort(left)
right = sort(right)
return merge(left, right)
}
// split array into two
func split(A []int) ([]int, []int) {
return A[0:len(A) / 2], A[len(A) / 2:]
}
// assumes that A and B are sorted
func merge(A, B []int) []int {
arr := make([]int, len(A) + len(B))
// index j for A, k for B
j, k := 0, 0
for i := 0; i < len(arr); i++ {
// fix for index out of range without using sentinel
if j >= len(A) {
arr[i] = B[k]
k++
continue
} else if k >= len(B) {
arr[i] = A[j]
j++
continue
}
// default loop condition
if A[j] > B[k] {
arr[i] = B[k]
k++
} else {
arr[i] = A[j]
j++
}
}
return arr
}


### Applications

• Merge Sort is useful for sorting linked lists in O(nLogn) time. Memory allocation differs from linked list to arrays. Unlike arrays, linked list nodes may not be adjacent in memory. Unlike array, in linked list, we can insert items in the middle in O(1) extra space and O(1) time. Therefore merge operation of merge sort can be implemented without extra space for linked lists.
• Counting inversions in a list
• Used in External Sorting

#### Alexa Ryder

Hi, I am creating the perfect textual information customized for learning. Message me for anything.