Scribd
Upload
3 views2 pages

Daa Program 4

The document provides a C++ program that implements the Merge Sort algorithm using the Divide and Conquer strategy. It includes methods for inputting an array of integers, merging sorted subarrays, sorting the entire array, and displaying the sorted result. The program sorts a user-defined number of elements and outputs the sorted array.

Uploaded by

RK
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
3 views2 pages

Daa Program 4

The document provides a C++ program that implements the Merge Sort algorithm using the Divide and Conquer strategy. It includes methods for inputting an array of integers, merging sorted subarrays, sorting the entire array, and displaying the sorted result. The program sorts a user-defined number of elements and outputs the sorted array.

Uploaded by

RK
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

4.

Write a program to sort an array of integers implementing Merge sort using Divide
and Conquer strategy.

#include <iostream>
using namespace std;

class MergeSort {
private:
int arr[100];
int n;

public:
void input() {
cout << "Enter number of elements: ";
cin >> n;

cout << "Enter elements:\n";


for (int i = 0; i < n; i++) {
cin >> arr[i];
}
}

void merge(int low, int mid, int high) {


int temp[100];
int i = low, j = mid + 1, k = low;

while (i <= mid && j <= high) {


if (arr[i] <= arr[j])
temp[k++] = arr[i++];
else
temp[k++] = arr[j++];
}

while (i <= mid)


temp[k++] = arr[i++];

while (j <= high)


temp[k++] = arr[j++];

for (int p = low; p <= high; p++)


arr[p] = temp[p];
}

void sort(int low, int high) {


if (low < high) {
int mid = (low + high) / 2;

sort(low, mid); // Divide left


sort(mid + 1, high); // Divide right
merge(low, mid, high); // Conquer
}
}

void display() {
cout << "Sorted array:\n";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
}

int getSize() {
return n;
}
};

int main() {
MergeSort m;
[Link]();
[Link](0, [Link]() - 1);
[Link]();
return 0;
}

Input:

Enter number of elements: 6


Enter elements:
38 27 43 3 9 82

Output:

Sorted array:
3 9 27 38 43 82

You might also like