Scribd
Upload
7 views2 pages

Merge

The document contains a C++ program that implements the merge sort algorithm to sort an array of integers. It defines a structure for nodes, functions to merge sorted halves, and perform merge sort. The main function demonstrates the sorting of a predefined array and outputs the original and sorted arrays.

Uploaded by

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

Merge

The document contains a C++ program that implements the merge sort algorithm to sort an array of integers. It defines a structure for nodes, functions to merge sorted halves, and perform merge sort. The main function demonstrates the sorting of a predefined array and outputs the original and sorted arrays.

Uploaded by

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

#include<iostream>

using namespace std;


struct node {
int data;
node* next;
};
// Function to merge two sorted halves
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left+1 ; // size of left half
int n2 = right - mid; // size of right half
// Temporary arrays
int L[n1], R[n2];

// Copy data to temp arrays


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 the temp arrays back into arr[]


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

// Copy any remaining elements


while (i < n1)
arr[k++] = L[i++];
while (j < n2)
arr[k++] = R[j++];
}

// Function to perform merge sort


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

// Sort first and second halves


mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);

// Merge the sorted halves


merge(arr, left, mid, right);
}
}
// Main program
int main() {
int arr[] = {38, 27, 43, 10,55,60};
int size = sizeof(arr) / sizeof(arr[0]);

cout << "Original array: ";


for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;

mergeSort(arr, 0, size - 1);

cout << "Sorted array: ";


for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;

return 0;
}

You might also like