Implementation of Merge Sort
// C++ program for Merge Sort
#include <bits/stdc++.h>
using namespace std;
// Merges two subarrays of array[].
// First subarray is arr[begin..mid]
// Second subarray is arr[mid+1..end]
void merge(int array[], int const left, int const mid,
int const right)
{
int const subArrayOne = mid - left + 1;
int const subArrayTwo = right - mid;
// Create temp arrays
auto *leftArray = new int[subArrayOne],
*rightArray = new int[subArrayTwo];
// Copy data to temp arrays leftArray[] and rightArray[]
for (auto i = 0; i < subArrayOne; i++)
leftArray[i] = array[left + i];
for (auto j = 0; j < subArrayTwo; j++)
rightArray[j] = array[mid + 1 + j];
auto indexOfSubArrayOne = 0, indexOfSubArrayTwo = 0;
int indexOfMergedArray = left;
// Merge the temp arrays back into array[left..right]
while (indexOfSubArrayOne < subArrayOne
&& indexOfSubArrayTwo < subArrayTwo) {
if (leftArray[indexOfSubArrayOne]
<= rightArray[indexOfSubArrayTwo]) {
array[indexOfMergedArray]
= leftArray[indexOfSubArrayOne];
indexOfSubArrayOne++;
}
else {
array[indexOfMergedArray]
= rightArray[indexOfSubArrayTwo];
indexOfSubArrayTwo++;
}
indexOfMergedArray++;
}
// Copy the remaining elements of
// left[], if there are any
while (indexOfSubArrayOne < subArrayOne) {
array[indexOfMergedArray]
= leftArray[indexOfSubArrayOne];
indexOfSubArrayOne++;
indexOfMergedArray++;
}
// Copy the remaining elements of
// right[], if there are any
while (indexOfSubArrayTwo < subArrayTwo) {
array[indexOfMergedArray]
= rightArray[indexOfSubArrayTwo];
indexOfSubArrayTwo++;
indexOfMergedArray++;
}
delete[] leftArray;
delete[] rightArray;
}
// begin is for left index and end is right index
// of the sub-array of arr to be sorted
void mergeSort(int array[], int const begin, int const end)
{
if (begin >= end)
return;
int mid = begin + (end - begin) / 2;
mergeSort(array, begin, mid);
mergeSort(array, mid + 1, end);
merge(array, begin, mid, end);
}
// UTILITY FUNCTIONS
// Function to print an array
void printArray(int A[], int size)
{
for (int i = 0; i < size; i++)
cout << A[i] << " ";
cout << endl;
}
// Driver code
int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int arr_size = sizeof(arr) / sizeof(arr[0]);
cout << "Given array is \n";
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
cout << "\nSorted array is \n";
printArray(arr, arr_size);
return 0;
}
// This code is contributed by Mayank Tyagi
// This code was revised by Joshua Estes
// C program for Merge Sort
#include <stdio.h>
#include <stdlib.h>
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
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;
j = 0;
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 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 right index of the
// sub-array of arr to be sorted
void mergeSort(int arr[], int l, int r)
{
if (l < r) {
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);
}
}
// Function to print an array
void printArray(int A[], int size)
{
int i;
for (i = 0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}
// Driver code
int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int arr_size = sizeof(arr) / sizeof(arr[0]);
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;
}
// Java program for Merge Sort
import java.io.*;
class MergeSort {
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
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
for (int i = 0; i < n1; ++i)
L[i] = arr[l + i];
for (int j = 0; j < n2; ++j)
R[j] = arr[m + 1 + j];
// Merge the temp arrays
// Initial indices of first and second subarrays
int i = 0, j = 0;
// Initial index of merged subarray 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()
void sort(int arr[], int l, int r)
{
if (l < r) {
// Find the middle point
int m = l + (r - l) / 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
static void printArray(int arr[])
{
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
// Driver code
public static void main(String args[])
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
System.out.println("Given array is");
printArray(arr);
MergeSort ob = new MergeSort();
ob.sort(arr, 0, arr.length - 1);
System.out.println("\nSorted array is");
printArray(arr);
}
}
/* This code is contributed by Rajat Mishra */
# Merges two subarrays of array[].
# First subarray is arr[left..mid]
# Second subarray is arr[mid+1..right]
def merge(array, left, mid, right):
subArrayOne = mid - left + 1
subArrayTwo = right - mid
# Create temp arrays
leftArray = [0] * subArrayOne
rightArray = [0] * subArrayTwo
# Copy data to temp arrays leftArray[] and rightArray[]
for i in range(subArrayOne):
leftArray[i] = array[left + i]
for j in range(subArrayTwo):
rightArray[j] = array[mid + 1 + j]
indexOfSubArrayOne = 0 # Initial index of first sub-array
indexOfSubArrayTwo = 0 # Initial index of second sub-array
indexOfMergedArray = left # Initial index of merged array
# Merge the temp arrays back into array[left..right]
while indexOfSubArrayOne < subArrayOne and indexOfSubArrayTwo < subArrayTwo:
if leftArray[indexOfSubArrayOne] <= rightArray[indexOfSubArrayTwo]:
array[indexOfMergedArray] = leftArray[indexOfSubArrayOne]
indexOfSubArrayOne += 1
else:
array[indexOfMergedArray] = rightArray[indexOfSubArrayTwo]
indexOfSubArrayTwo += 1
indexOfMergedArray += 1
# Copy the remaining elements of left[], if any
while indexOfSubArrayOne < subArrayOne:
array[indexOfMergedArray] = leftArray[indexOfSubArrayOne]
indexOfSubArrayOne += 1
indexOfMergedArray += 1
# Copy the remaining elements of right[], if any
while indexOfSubArrayTwo < subArrayTwo:
array[indexOfMergedArray] = rightArray[indexOfSubArrayTwo]
indexOfSubArrayTwo += 1
indexOfMergedArray += 1
# begin is for left index and end is right index
# of the sub-array of arr to be sorted
def mergeSort(array, begin, end):
if begin >= end:
return
mid = begin + (end - begin) // 2
mergeSort(array, begin, mid)
mergeSort(array, mid + 1, end)
merge(array, begin, mid, end)
# Function to print an array
def printArray(array, size):
for i in range(size):
print(array[i], end=" ")
print()
# Driver code
if __name__ == "__main__":
arr = [12, 11, 13, 5, 6, 7]
arr_size = len(arr)
print("Given array is")
printArray(arr, arr_size)
mergeSort(arr, 0, arr_size - 1)
print("\nSorted array is")
printArray(arr, arr_size)
// C# program for Merge Sort
using System;
class MergeSort {
// Merges two subarrays of []arr.
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
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];
int i, j;
// Copy data to temp arrays
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
// Initial indexes of first
// and second subarrays
i = 0;
j = 0;
// Initial index of merged
// subarray 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()
void sort(int[] arr, int l, int r)
{
if (l < r) {
// Find the middle point
int m = l + (r - l) / 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
static void printArray(int[] arr)
{
int n = arr.Length;
for (int i = 0; i < n; ++i)
Console.Write(arr[i] + " ");
Console.WriteLine();
}
// Driver code
public static void Main(String[] args)
{
int[] arr = { 12, 11, 13, 5, 6, 7 };
Console.WriteLine("Given array is");
printArray(arr);
MergeSort ob = new MergeSort();
ob.sort(arr, 0, arr.Length - 1);
Console.WriteLine("\nSorted array is");
printArray(arr);
}
}
// This code is contributed by Princi Singh
// JavaScript program for Merge Sort
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
function merge(arr, l, m, r)
{
var n1 = m - l + 1;
var n2 = r - m;
// Create temp arrays
var L = new Array(n1);
var R = new Array(n2);
// Copy data to temp arrays L[] and R[]
for (var i = 0; i < n1; i++)
L[i] = arr[l + i];
for (var j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
// Merge the temp arrays back into arr[l..r]
// Initial index of first subarray
var i = 0;
// Initial index of second subarray
var j = 0;
// Initial index of merged subarray
var 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 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
// right index of the sub-array
// of arr to be sorted
function mergeSort(arr,l, r){
if(l>=r){
return;
}
var m =l+ parseInt((r-l)/2);
mergeSort(arr,l,m);
mergeSort(arr,m+1,r);
merge(arr,l,m,r);
}
// Function to print an array
function printArray( A, size)
{
for (var i = 0; i < size; i++)
console.log( A[i] + " ");
}
var arr = [ 12, 11, 13, 5, 6, 7 ];
var arr_size = arr.length;
console.log( "Given array is ");
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
console.log( "Sorted array is ");
printArray(arr, arr_size);
// This code is contributed by SoumikMondal
<?php
/* PHP recursive program for Merge Sort */
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
function merge(&$arr, $l, $m, $r)
{
$n1 = $m - $l + 1;
$n2 = $r - $m;
// Create temp arrays
$L = array();
$R = array();
// 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;
$j = 0;
$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 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 right index of the
// sub-array of arr to be sorted
function mergeSort(&$arr, $l, $r)
{
if ($l < $r) {
$m = $l + (int)(($r - $l) / 2);
// Sort first and second halves
mergeSort($arr, $l, $m);
mergeSort($arr, $m + 1, $r);
merge($arr, $l, $m, $r);
}
}
// Function to print an array
function printArray($A, $size)
{
for ($i = 0; $i < $size; $i++)
echo $A[$i]." ";
echo "\n";
}
// Driver code
$arr = array(12, 11, 13, 5, 6, 7);
$arr_size = sizeof($arr);
echo "Given array is \n";
printArray($arr, $arr_size);
mergeSort($arr, 0, $arr_size - 1);
echo "\nSorted array is \n";
printArray($arr, $arr_size);
return 0;
//This code is contributed by Susobhan Akhuli
?>
Output
Given array is 12 11 13 5 6 7 Sorted array is 5 6 7 11 12 13
Merge Sort – Data Structure and Algorithms Tutorials
Merge sort is a sorting algorithm that follows the divide-and-conquer approach. It works by recursively dividing the input array into smaller subarrays and sorting those subarrays then merging them back together to obtain the sorted array.
In simple terms, we can say that the process of merge sort is to divide the array into two halves, sort each half, and then merge the sorted halves back together. This process is repeated until the entire array is sorted.