Scribd
Upload
7 views3 pages

Step-by-Step Merge Sort Guide

The document outlines the Merge Sort algorithm, detailing its recursive and iterative processes for sorting an array. It includes step-by-step instructions for the MERGE_SORT function and the MERGE function, as well as a C++ implementation for user input and output of a sorted array. The algorithm works by dividing the array into halves, sorting them, and merging them back together in sorted order.

Uploaded by

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

Step-by-Step Merge Sort Guide

The document outlines the Merge Sort algorithm, detailing its recursive and iterative processes for sorting an array. It includes step-by-step instructions for the MERGE_SORT function and the MERGE function, as well as a C++ implementation for user input and output of a sorted array. The algorithm works by dividing the array into halves, sorting them, and merging them back together in sorted order.

Uploaded by

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

Merge Sort Algorithm (Step by Step)

Algorithm: MERGE_SORT(arr, low, high)

1. If low < high


a. Find the middle point → mid = (low + high) / 2
b. Recursively call MERGE_SORT(arr, low, mid)
c. Recursively call MERGE_SORT(arr, mid+1, high)
d. Call MERGE(arr, low, mid, high) to merge the two halves

Algorithm: MERGE(arr, low, mid, high)

1. Create two temporary arrays:


o Left[] = arr[low … mid]
o Right[] = arr[mid+1 … high]
2. Compare elements of Left[] and Right[], copy the smaller element into arr[]
3. Copy remaining elements of Left[] (if any)
4. Copy remaining elements of Right[] (if any)

#include <iostream>

using namespace std;

int main() {

int n;

cout << "Enter number of elements: ";

cin >> n;

int arr[100]; // assuming max 100 elements

cout << "Enter elements: ";

for (int i = 0; i < n; i++)

cin >> arr[i];

// ---------- Merge Sort Process ----------

// Recursive calls simulated with inline code

int size = 1; // start with subarrays of size 1


while (size < n) {

for (int left = 0; left < n - size; left += 2 * size) {

int mid = left + size - 1;

int right = min(left + 2 * size - 1, n - 1);

// Create temporary arrays

int n1 = mid - left + 1;

int n2 = right - mid;

int L[50], R[50]; // temporary storage

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];

// Merge step

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

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


while (i < n1) {

arr[k] = L[i];

i++; k++;

while (j < n2) {

arr[k] = R[j];

j++; k++;

size = size * 2; // double subarray size

// ---------- Print Sorted Array ----------

cout << "Sorted array: ";

for (int i = 0; i < n; i++)

cout << arr[i] << " ";

cout << endl;

return 0;

You might also like