Scribd
Upload
19 views5 pages

Week - 2 & 3 With Coding Spring'26

This document serves as a lab manual for CSC2211 Algorithms at AIUB, focusing on recursion and recursive algorithms, specifically Merge Sort and Counting Sort. It outlines the prerequisites for understanding the material, provides a theoretical explanation of Merge Sort, and includes pseudocode along with C++ code for its implementation. The manual aims to equip students with knowledge on sorting algorithms through practical coding exercises.

Uploaded by

yeashimportantdocument
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
19 views5 pages

Week - 2 & 3 With Coding Spring'26

This document serves as a lab manual for CSC2211 Algorithms at AIUB, focusing on recursion and recursive algorithms, specifically Merge Sort and Counting Sort. It outlines the prerequisites for understanding the material, provides a theoretical explanation of Merge Sort, and includes pseudocode along with C++ code for its implementation. The manual aims to equip students with knowledge on sorting algorithms through practical coding exercises.

Uploaded by

yeashimportantdocument
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

AMERICAN INTERNATIONAL UNIVERSITY-BANGLADESH (AIUB)

FACULTY OF SCIENCE & TECHNOLOGY


DEPARTMENT OF COMPUTER SCIENCE

LAB MANUAL 02 & 03


CSC2211 Algorithms
Fall 2025-2026
TITLE

An Introduction to Recursion and Recursive Algorithm

PREREQUISITE

• Have a clear understanding of Stack


• Know how to analyze the runtime of algorithms
• Have a clear understanding of return statement

OBJECTIVE

• To know about Merge Sort


• To know about Counting Sort

THEORY

Merge Sort is a classic, efficient, and stable sorting algorithm based on the divide and conquer paradigm. It
works by recursively dividing the unsorted list into smaller sublists until each sublist contains only one
element, then merges the sublists in a sorted manner to produce the sorted list. Here’s a step-by-step
breakdown:
Steps in Merge Sort
1. Divide: The list is divided into two halves. This process continues recursively until each sublist
contains a single element (which is inherently sorted).
2. Conquer (Sort and Merge): Each pair of sublists is then merged back together in sorted order. This
merging step continues until all sublists are merged back into one single sorted list.
Pseudocode for Merge Sort

C++ Code to Implement Merge Sort

#include<iostream>
using namespace std;

void merge(int arr[], int l, int m, int r)


{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;

/* create temp arrays */


int L[n1], R[n2];

/* Copy data to temp arrays L[] and R[] */


for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];

/* Merge the temp arrays back into arr[l..r]*/


i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}

/* Copy the remaining elements of L[], if there


are any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}

/* Copy the remaining elements of R[], if there


are any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}

/* l is for left index and r is right index of the


sub-array of arr to be sorted */

void mergeSort(int arr[], int l, int r)


{
if (l < r)
{
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l+(r-l)/2;
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);

merge(arr, l, m, r);
}
}

void printArray(int A[], int size)


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

int main()
{
int n,x,i;
cout<<"Enter size of array: ";
cin>>n;
int arr[n];
cout<<"Enter Array Elements: ";
for(i=0;i<n;i++)
{
cin>>arr[i];
}
mergeSort(arr, 0, n - 1);

cout<<"\nSorted array is \n";


printArray(arr, n);
return 0;

You might also like