Scribd
Upload
10 views5 pages

Merge Sort

The document outlines the Merge Sort algorithm, providing a detailed explanation of its recursive structure and merging process. It includes both pseudocode and C++ code implementation for sorting an array. The code prompts the user to input the number of elements and the elements themselves, then outputs the sorted array.

Uploaded by

deepanshuy1895
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
10 views5 pages

Merge Sort

The document outlines the Merge Sort algorithm, providing a detailed explanation of its recursive structure and merging process. It includes both pseudocode and C++ code implementation for sorting an array. The code prompts the user to input the number of elements and the elements themselves, then outputs the sorted array.

Uploaded by

deepanshuy1895
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 5

Aim : Merge Sort

Date : 11/09/2025

Algorithm:

MERGE_SORT(A, left, right)


if left < right then
mid = (left + right) / 2
MERGE_SORT(A, left, mid)
MERGE_SORT(A, mid + 1, right)
MERGE(A, left, mid, right)
end if MERGE(A, left, mid, right)
n1 = mid - left + 1
n2 = right - mid
create arrays L[1..n1], R[1..n2]
for i = 1 to n1
L[i] = A[left + i - 1]
for j = 1 to n2
R[j] = A[mid + j]
i = 1, j = 1, k = left
while i ≤ n1 and j ≤ n2 do
if L[i] ≤ R[j]
then A[k] = L[i] i = i + 1
else A[k] = R[j] j = j + 1
end if k = k + 1
end while
while i ≤ n1
do A[k] = L[i]
i=i+1
k=k+1
end while
while j ≤ n2
do A[k] = R[j]
j=j+1
k=k+1
end while

Code :

#include using namespace std;


void merge(int arr[], int left, int mid, int right)
{
int n1 = mid - left + 1;
int n2 = right - mid;
int* L = new int[n1];
int* R = new int[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{ arr[k++] = L[i++]; }
else { arr[k++] = R[j++]; } }
while (i < n1)
arr[k++] = L[i++];
while (j < n2)
arr[k++] = R[j++];
delete[] L;
delete[] R;
}
void mergeSort(int arr[], int left, int right)
{ if (left < right)
{ int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
int main()
{
int n;
cout << "Enter number of elements: ";
cin >> n;
int* arr = new int[n];
cout << "Enter elements: ";
for (int i = 0; i < n; i++)
cin >> arr[i];
mergeSort(arr, 0, n - 1);
cout << "Sorted array: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
delete[] arr;
return 0;
}
Output:

You might also like