Algorithm Speed (2.00) :

Array Size (100) :

Merge Sort :

Author(s) : John von Neumann Date : 1945

Merge sort is another divide-and-conquer algorithm that excels in sorting linked lists or arrays. It works by recursively dividing the input data structure into smaller sub-arrays containing a single element each (base case). In the merge phase, adjacent sub-arrays are combined while maintaining the sorted order. This is achieved by comparing elements from both sub-arrays and inserting the smaller one into the final merged sub-array. This process continues until all sub-arrays are merged into a single sorted array.

Time Complexity	O(n log n)
Best Case	O(n log n)
Worst Case	O(n log n)
Space Complexity	O(n)
Stable	Yes

def merge(arr, left, mid, right):
	n1 = mid - left + 1
	n2 = right - mid

	left_arr = [0] * n1
	right_arr = [0] * n2

	for i in range(0, n1):
		left_arr[i] = arr[left + i]
	for j in range(0, n2):
		right_arr[j] = arr[mid + 1 + j]

	i = 0
	j = 0
	k = left

	while i < n1 and j < n2:
		if left_arr[i] <= right_arr[j]:
			arr[k] = left_arr[i]
			i += 1
		else:
			arr[k] = right_arr[j]
			j += 1
		k += 1

	while i < n1:
		arr[k] = left_arr[i]
		i += 1
		k += 1

	while j < n2:
		arr[k] = right_arr[j]
		j += 1
		k += 1

def merge_sort(arr, left, right):
	if left < right:
		m = left + (right - left) // 2
		merge_sort(arr, left, m)
		merge_sort(arr, m + 1, right)
		merge(arr, left, m, right)

# Test array
arr = [12, 11, 13, 5, 6, 7]
merge_sort(arr, 0, len(arr) - 1)
print('Sorted array is:', arr)

function merge(arr, left, mid, right) {
	let n1 = mid - left + 1;
	let n2 = right - mid;

	let leftArr = new Array(n1);
	let rightArr = new Array(n2);

	for (let i = 0; i < n1; i++) {
		leftArr[i] = arr[left + i];
	}
	for (let j = 0; j < n2; j++) {
		rightArr[j] = arr[mid + 1 + j];
	}

	let i = 0;
	let j = 0;
	let k = left;

	while (i < n1 && j < n2) {
		if (leftArr[i] <= rightArr[j]) {
			arr[k] = leftArr[i];
			i++;
		} else {
			arr[k] = rightArr[j];
			j++;
		}
		k++;
	}

	while (i < n1) {
		arr[k] = leftArr[i];
		i++;
		k++;
	}

	while (j < n2) {
		arr[k] = rightArr[j];
		j++;
		k++;
	}
}

function mergeSort(arr, left, right) {
	if (left < right) {
		let m = left + Math.floor((right - left) / 2);
		mergeSort(arr, left, m);
		mergeSort(arr, m + 1, right);
		merge(arr, left, m, right);
	}
}

// Test array
let arr = [12, 11, 13, 5, 6, 7];
mergeSort(arr, 0, arr.length - 1);
console.log('Sorted array is:', arr);

public class MergeSort {
	public static void merge(int[] arr, int left, int mid, int right) {
		int n1 = mid - left + 1;
		int n2 = right - mid;

		int[] leftArr = new int[n1];
		int[] rightArr = new int[n2];

		for (int i = 0; i < n1; i++) {
			leftArr[i] = arr[left + i];
		}
		for (int j = 0; j < n2; j++) {
			rightArr[j] = arr[mid + 1 + j];
		}

		int i = 0, j = 0, k = left;
		while (i < n1 && j < n2) {
			if (leftArr[i] <= rightArr[j]) {
				arr[k] = leftArr[i];
				i++;
			} else {
				arr[k] = rightArr[j];
				j++;
			}
			k++;
		}

		while (i < n1) {
			arr[k] = leftArr[i];
			i++;
			k++;
		}

		while (j < n2) {
			arr[k] = rightArr[j];
			j++;
			k++;
		}
	}

	public static void mergeSort(int[] arr, int left, int right) {
		if (left < right) {
			int mid = left + (right - left) / 2;
			mergeSort(arr, left, mid);
			mergeSort(arr, mid + 1, right);
			merge(arr, left, mid, right);
		}
	}

	public static void main(String[] args) {
		int[] arr = {12, 11, 13, 5, 6, 7};
		mergeSort(arr, 0, arr.length - 1);

		System.out.print("Sorted array is: ");
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}
}

package main

import (
	"fmt"
)

func merge(arr []int, left, mid, right int) {
	n1 := mid - left + 1
	n2 := right - mid

	leftArr := make([]int, n1)
	rightArr := make([]int, n2)

	copy(leftArr, arr[left:left+n1])
	copy(rightArr, arr[mid+1:right+1])

	i := 0
	j := 0
	k := left

	for i < n1 && j < n2 {
		if leftArr[i] <= rightArr[j] {
			arr[k] = leftArr[i]
			i++
		} else {
			arr[k] = rightArr[j]
			j++
		}
		k++
	}

	for i < n1 {
		arr[k] = leftArr[i]
			i++
		k++
	}

	for j < n2 {
		arr[k] = rightArr[j]
			j++
		k++
	}
}

func mergeSort(arr []int, left, right int) {
	if left < right {
		m := left + (right-left)/2
		mergeSort(arr, left, m)
		mergeSort(arr, m+1, right)
		merge(arr, left, m, right)
	}
}

func main() {
	arr := []int{12, 11, 13, 5, 6, 7}
	mergeSort(arr, 0, len(arr)-1)

	fmt.Println("Sorted array is: ", arr)
}

#include <stdio.h>

void merge(int arr[], int left, int mid, int right) {
	int n1 = mid - left + 1;
	int n2 = right - mid;

	int leftArr[n1], rightArr[n2];

	for (int i = 0; i < n1; i++) {
		leftArr[i] = arr[left + i];
	}
	for (int j = 0; j < n2; j++) {
		rightArr[j] = arr[mid + 1 + j];
	}

	int i = 0, j = 0, k = left;

	while (i < n1 && j < n2) {
		if (leftArr[i] <= rightArr[j]) {
			arr[k] = leftArr[i];
			i++;
		} else {
			arr[k] = rightArr[j];
			j++;
		}
		k++;
	}

	while (i < n1) {
		arr[k] = leftArr[i];
			i++;
		k++;
	}

	while (j < n2) {
		arr[k] = rightArr[j];
			j++;
		k++;
	}
}

void mergeSort(int arr[], int left, int right) {
	if (left < right) {
		int mid = left + (right - left) / 2;
		mergeSort(arr, left, mid);
		mergeSort(arr, mid + 1, right);
		merge(arr, left, mid, right);
	}
}

int main() {
	int arr[] = {12, 11, 13, 5, 6, 7};
	int n = sizeof(arr) / sizeof(arr[0]);
	mergeSort(arr, 0, n - 1);
	printf("Sorted array is: ");
	for (int i = 0; i < n; i++) {
		printf("%d ", arr[i]);
	}
	return 0;