# Merge SORT ALGORITHM

Contents

## INTRODUCTION

In this tutorial, we will learn about the Merge SORT ALGORITHM.

Sorting is one of the fundamental operations in computer science, and there are numerous sorting algorithms available. Merge sort is one such algorithm, which is efficient and widely used in programming languages. In this article, we will discuss the merge sort algorithm and its implementation in C++, Java, and Python.

Merge sort is a divide-and-conquer algorithm that sorts an array by dividing it into two halves, sorting each half, and then merging the two halves. It is a stable sorting algorithm, meaning that it maintains the relative order of equal elements. Merge sort has a time complexity of O(nlogn), where n is the number of elements to be sorted.

The merge sort algorithm can be divided into two main steps: the divide step and the merge step. In the divide step, the array is divided into two halves, and each half is sorted recursively using merge sort. In the merge step, the two sorted halves are merged to produce the final sorted array.

Now let’s see the implementation of the merge sort algorithm in C++, Java, and Python.

## C++ Implementation:

```#include <iostream>
using namespace std;

void merge(int arr[], int l, int m, int r)
{
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
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];
int 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++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}

void mergeSort(int arr[], int l, int r)
{
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}

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

```

In the above C++ code, the `merge()` function takes three parameters: the array, the starting index of the first subarray, the ending index of the first subarray, and the ending index of the second subarray. The function first copies the elements of the two subarrays into two separate arrays, `L` and `R`, and then merges the two arrays into the original array `arr`. The `mergeSort()` the function is the main function that calls itself recursively to sort the array.

## Java Implementation:

```class MergeSort {
void merge(int arr[], int l, int m, int r)
{
int n1 = m - l + 1;
int n2 = r - m + 1;
int L[] = new int[n1];
int R[] = new int[n2];
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];
int i = 0, j = 0;
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++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int l, int r)
{
if (l < r) {
int m = (l + r) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
public static void main(String args[])
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int arr_size = arr.length;
MergeSort ob = new MergeSort();
ob.mergeSort(arr, 0, arr_size - 1);
System.out.println("Sorted array:");
for (int i = 0; i < arr_size; ++i)
System.out.print(arr[i] + " ");
}
}

```

In the above Java code, the `merge()` function is similar to the C++ code. The `mergeSort()` function is the main function that calls itself recursively to sort the array. In the `main()` function, we create an object of the `MergeSort` class and call the `mergeSort()` function to sort the array.

Python Implementation:

```def merge(arr, l, m, r):
n1 = m - l + 1
n2 = r- m
L = [0] * (n1)
R = [0] * (n2)
for i in range(0, n1):
L[i] = arr[l + i]
for j in range(0, n2):
R[j] = arr[m + 1 + j]
i = 0
j = 0
k = l
while i < n1 and j < n2:
if L[i] <= R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
while i < n1:
arr[k] = L[i]
i += 1
k += 1
while j < n2:
arr[k] = R[j]
j += 1
k += 1

def mergeSort(arr, l, r):
if l < r:
m = (l+(r-1))//2
mergeSort(arr, l, m)
mergeSort(arr, m+1, r)
merge(arr, l, m, r)

arr = [12, 11, 13, 5, 6, 7]
n = len(arr)
mergeSort(arr, 0, n-1)
print("Sorted array:")
for i in range(n):
print(arr[i], end=" ")

```

In the above Python code, the `merge()` function is the same as the C++ and Java code. The `mergeSort()` function is the main function that calls itself recursively to sort the array. In the `main()` function, we create an array and call the `mergeSort()` function to sort the array. Finally, we print the sorted array using a `for` loop.

In the above Python code, the `mergeSort()` function takes an array as input and recursively sorts the array by dividing it into two halves. The `merge()` step is similar to the C++ and Java code. In the `main()` function, we create an array and call the `mergeSort()` function to sort the array.