Program for Merge Sort PDF

Preview

Summary

Merge sort program with time complexity....

Description

Merge Sort Student Name:Rahul Jain UID: 21MCA2923 Branch: MCA Section/Group:5A Semester: 1 Semester Date of Performance: 07/11/2021 Subject Name: Design and Analysis of Algorithms Lab Subject Code: 21CAP-606

1.

Aim/Overview of the practical: To sort an array using merge sort technique.

2.

Task to be done: Write a program to count & display number of exchanges while implementing merge sort for worst case, average case and best case.

3.

Algorithm/Flowchart : Step 1 − if it is only one element in the list it is already sorted, return. Step 2 − divide the list recursively into two halves until it can no more be divided. Step 3 − merge the smaller lists into new list in sorted order

4.

8

Dataset: 1

4

9

5. Code for experiment/practical: #include using namespace std;

6

3

5

2

7

0

int merge(int arr[], int l, int m, int r) { int count = 0; int i, j, k; int n1 = m - l + 1; int n2 = r - m; int L[n1], R[n2]; for (i = 0; i < n1; i++) L[i] = arr[l + i]; for (j = 0; j < n2; j++) R[j] = arr[m + 1 + j]; i = 0; j = 0; k = l; while (i < n1 && j < n2) { if (L[i]...