INDEX

S No. Experiment Date Page No. Signature

To write a program to implement

1[A] Linear Search algorithm to find a 20-08-2025 2-4
given element in a list or array

Program for Recursive Binary

Search To write a program to
1[B] implement Binary Search algorithm 20-08-2025 5-7
to find a given element in a list or
array

To write a program to implement

Bubble Sort algorithm to arrange
2 03-09-2025 8-9
elements of an array in ascending
order.

To write a program to implement

Selection Sort algorithm to arrange
3 10-09-2025 10-11
elements of an array in ascending
order

To write a program to implement

Insertion Sort algorithm to arrange
4 17-09-2025 12-15
elements of an array in ascending
order for Insertion Sort

To write a program to implement

Shell Sort algorithm to arrange
5 24-09-2025 16-18
elements of an array in ascending
order

To write a program to implement

Quick Sort algorithm to arrange
6 08-10-2025 19-22
elements of an array in ascending
order

To write a program to implement

Merge Sort algorithm to arrange
7 15-10-2025 23-26
elements of an array in ascending
order

To write programs to find the

Minimum Spanning Tree (MST) of a
connected, weighted, undirected
8 29-10-2025
graph using
1. Kruskal’s Algorithm,
2. Prim’s Algorithm

1
 Experiment no.: - 1[a]

LINEAR SEARCH is a simple search algorithm that sequentially checks each

element of the list until a match is found or the whole list has been searched. It is
also known as a sequential search.

INPUT CODE

#include <stdio.h>

int linear_search(int arr[], int n, int target) {

for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i; // Element found, return its index
}
}
return -1; // Element not found
}

int main() {
int arr[] = {10, 20, 80, 30, 60, 50, 110, 100, 130, 170};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 110;printf("Original array: \n");

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

printf("%d ", arr[i]);

printf("\n");

int result = linear_search(arr, n, target);

if (result != -1) {

printf("Element %d found at index %d\n", target, result);

} else {

printf("Element %d not found in the array\n", target);

2
 target = 99; // Test for an element not in the array

result = linear_search(arr, n, target);

if (result != -1) {

printf("Element %d found at index %d\n", target, result);

} else {

printf("Element %d not found in the array\n", target);

return 0;

OUTPUT

Original array: 10 20 80 30 60 50 110 100 130 170

Element 110 found at index 6

Element 99 not found in the array

COMPLEXITY

The complexity of Linear Search is straightforward and depends directly on the

number of elements in the list and the position of the target element (if present).

Time Complexity:

1. Worst Case: O(n): The worst-case scenario occurs when:

* The target element is at the very end of the list.

* The target element is not present in the list at all.

In both these situations, the algorithm has to traverse the entire list, performing 'n'
comparisons (where 'n' is the number of elements in the array). Hence, the time
complexity is linear, O(n).

2. Average Case: O(n): On average, if the target element is present in the list, it is
expected to be found somewhere in the middle. This means, on average, the

3
algorithm will perform approximately n/2 comparisons. Since Big O notation discards
constant factors, the average-case time complexity is also O(n).

3. Best Case: O(1): The best-case scenario occurs when the target element is the
very first element in the list. In this case, the algorithm finds the element with just one
comparison. Hence, the time complexity is constant, O(1).

Space Complexity: O(1) - Linear Search is an in-place algorithm. It only requires a

constant amount of extra space for a few variables (like the loop counter `i` and the
`target` variable). It does not require any additional data structures whose size grows
with the input size.

4
 Experiment no.: - 1[b]

BINARY SEARCH is an efficient algorithm for finding an item from a sorted list of
items. It works by repeatedly dividing in half the portion of the list that could contain
the item, until you've narrowed down the possible locations to just one. For Binary
Search to work, the data structure must be sorted.

INPUT CODE

#include <stdio.h>

int binary_search(int arr[], int low, int high, int target) {

while (low <= high) {

int mid = low + (high - low) / 2; // Calculate mid to prevent overflow

// Check if target is present at mid

if (arr[mid] == target) {

return mid;

// If target is greater, ignore left half

if (arr[mid] < target) {

low = mid + 1;

// If target is smaller, ignore right half

else {

high = mid - 1;

return -1; // Element not found

5
}

int main() {

int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};

int n = sizeof(arr) / sizeof(arr[0]);

int target = 70;

printf("Original array: \n");

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

printf("%d ", arr[i]);

printf("\n");

int result = binary_search(arr, 0, n - 1, target);

if (result != -1) {

printf("Element %d found at index %d\n", target, result);

} else {

printf("Element %d not found in the array\n", target);

target = 35; // Test for an element not in the array

result = binary_search(arr, 0, n - 1, target);

if (result != -1) {

printf("Element %d found at index %d\n", target, result);

} else {

printf("Element %d not found in the array\n", target);

6
 return 0;

OUTPUT

Original array: 10 20 30 40 50 60 70 80 90 100

Element 70 found at index 6
Element 35 not found in the array

COMPLEXITY

The complexity of Binary Search is a classic example of a logarithmic time algorithm

due to its divide-and-conquer strategy.

Time Complexity:

1. Worst Case: O(log n)

The worst-case scenario occurs when the target element is not in the array, or
it is found at the very last comparison (e.g., the element is the last one
remaining after many divisions). In each step, the search space is halved.
For an array of size 'n', it takes 'k' comparisons until the search space is
reduced to 1 element, where 2^k = n. Therefore, k = log₂n. This makes the
worst-case time complexity O(log n).
2. Average Case: O(log n)
On average, Binary Search will perform a number of comparisons proportional
to the logarithm of the number of elements. The halving of the search space
at each step ensures that the average case performance remains logarithmic.
3. Best Case: O(1)
The best-case scenario occurs when the target element is found at the middle
of the array in the very first comparison. In this case, the algorithm makes only
one comparison. Hence, the time complexity is constant, O(1).

Space Complexity:

● Iterative Version: O(1)

The iterative implementation of Binary Search is an in-place algorithm. It only
requires a constant amount of extra space for a few variables (like low, high,
mid, and target). It does not require any additional data structures whose
size grows with the input size.
● Recursive Version: O(log n)
If implemented recursively, Binary Search uses the call stack. In the worst
case, the depth of the recursion stack will be proportional to log n (because
the problem size is halved in each recursive call). Therefore, the space
complexity for the recursive version is O(log n).

7
8
 Experiment no.: - 2

BUBBLE SORT is a simple sorting algorithm that repeatedly steps through the
list, compares adjacent elements, and swaps them if they are in the wrong order.
The pass through the list is repeated until no swaps are needed, which indicates that
the list is sorted. It gets its name because smaller elements "bubble" to the top (or
beginning) of the list with each pass.

INPUT CODE
#include <stdio.h>

void bubble_sort(int arr[], int n) {

for (int i = 0; i < n - 1; i++) {
// Last i elements are already in place
for (int j = 0; j < n - i - 1; j++) {
// Traverse the array from 0 to n-i-1
// Swap if the element found is greater
// than the next element
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Original array: \n");

for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");

bubble_sort(arr, n);

printf("Sorted array: \n");

for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");

return 0;
}

9
OUTPUT
Original array: 64 34 25 12 22 11 90

Sorted array: 11 12 22 25 34 64 90

HOW THE COMPLEXITY IS DERIVED

The complexity of Bubble Sort is primarily determined by the nested loops in its
implementation.
1. Outer Loop: This loop runs n-1 times, where n is the number of elements in
the array. This loop ensures that each element, from the beginning to the
second to last, gets a chance to "bubble" to its correct position.
2. Inner Loop: This loop's iterations decrease with each pass of the outer loop.
○ In the first pass (i=0), the inner loop runs n-1 times.
○ In the second pass (i=1), it runs n-2 times.
○ ...and so on, until the last pass where it runs 1 time.
Total Number of Comparisons and Swaps (Worst/Average Case):
The total number of comparisons in the worst and average cases can be
approximated by the sum:
(n-1) + (n-2) + ... + 1
This is an arithmetic series, and its sum is given by the formula: n * (n-1) / 2.
For large n, this simplifies to approximately n^2 / 2.
Since we drop constant factors and lower-order terms in Big O notation, both the
worst-case and average-case time complexities are O(n^2).

Best Case Complexity:

The best-case scenario occurs when the array is already sorted. In this optimized
version of Bubble Sort (which usually includes a flag to check if any swaps occurred
in a pass), the algorithm would make one full pass through the array, find no swaps,
and then terminate. This would involve n-1 comparisons, leading to a best-case time
complexity of O(n).

Space Complexity:
Bubble Sort is an in-place sorting algorithm because it only requires a constant
amount of extra space for temporary variables (like temp during a swap). Therefore,
its space complexity is O(1).

10
 Experiment no.: - 3

Selection Sort algorithm sorts an array by repeatedly finding the minimum

element (considering ascending order) from the unsorted part and putting it at the
beginning. The algorithm maintains two subarrays in a given array:

1. The subarray which is already sorted.

2. The remaining subarray which is unsorted.
In every iteration of selection sort, the minimum element from the unsorted
subarray is picked and moved to the sorted subarray.

INPUT CODE
#include <stdio.h>

void selection_sort(int arr[], int n) {

int i, j, min_idx;

for (i = 0; i < n - 1; i++) {

min_idx = i;

for (j = i + 1; j < n; j++) {

if (arr[j] < arr[min_idx])

min_idx = j;
}

int temp = arr[min_idx];

arr[min_idx] = arr[i];

arr[i] = temp;

int main() {

int arr[] = {64, 25, 12, 22, 11};

int n = sizeof(arr) / sizeof(arr[0]);

printf("Original array: \n");

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

11
 printf("%d ", arr[i]);

printf("\n");

selection_sort(arr, n);

printf("Sorted array: \n");

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

printf("%d ", arr[i]);

printf("\n");

return 0;

OUTPUT
Original array: 12 11 13 5 6
Sorted array: 5 6 11 12 13

COMPLEXITY
The complexity of Selection Sort is primarily determined by its nested loop structure.

1. Outer Loop: This loop runs n-1 times, where n is the number of elements in
the array. Its purpose is to iterate through the unsorted portion of the array,
placing one element into its correctly sorted position in each pass.
2. Inner Loop: This loop is responsible for finding the minimum element in the
remaining unsorted subarray.
○ In the first pass of the outer loop (i = 0), the inner loop runs n-1
times (comparing arr[1] to arr[n-1]).
○ In the second pass (i = 1), the inner loop runs n-2 times.
○ ...and so on, until the last pass (i = n-2), where it runs 1 time.

Total Number of Comparisons:

The total number of comparisons in Selection Sort can be calculated by summing
the iterations of the inner loop:

(n-1) + (n-2) + ... + 1

This is an arithmetic series, and its sum is given by the formula: n * (n-1) / 2.
For large n, this simplifies to approximately n^2 / 2.

12
Since Big O notation discards constant factors and lower-order terms, the time
complexity for comparisons is O(n^2).

Total Number of Swaps:

Unlike other sorting algorithms, Selection Sort performs a minimal number of swaps.
In each pass of the outer loop, it performs at most one swap (to place the minimum
element found into its correct position).
Therefore, for an array of size n, Selection Sort performs exactly n-1 swaps.\
Since n-1 is proportional to n, the swap complexity is O(n).

Overall Time Complexity:

When considering the dominant operation (comparisons), the time complexity of

Selection Sort is O(n^2). This holds true for the worst, average, and best cases
because the algorithm always performs the same number of comparisons regardless
of the initial arrangement of elements. It will always iterate through the entire
unsorted portion to find the minimum element.

Space Complexity:

Selection Sort is an in-place sorting algorithm. It only requires a constant amount of

extra space for temporary variables (like min_idx and temp during a swap).
Therefore, its space complexity is O(1).

13
 Experiment no.: - 4

INSERTION SORT builds the final sorted array (or list) one item at a time. It
iterates through the input elements and removes one element at each iteration, finds
the place where it belongs within the already sorted part of the array, and inserts it
there. It's efficient for small data sets and works well with nearly sorted data.

INPUT CODE
void insertion_sort(int arr[], int n) {

int i, key, j;

for (i = 1; i < n; i++) {

key = arr[i];

j = i - 1;

// Move elements of arr[0..i-1], that are

// greater than key, to one position ahead

// of their current position

while (j >= 0 && arr[j] > key) {

arr[j + 1] = arr[j];

j = j - 1;
}
arr[j + 1] = key;
}
}

int main() {

int arr[] = {12, 11, 13, 5, 6};

int n = sizeof(arr) / sizeof(arr[0]);

printf("Original array: \n");

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

printf("%d ", arr[i]);

}

printf("\n");

14
 insertion_sort(arr, n);

printf("Sorted array: \n");

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

printf("%d ", arr[i]);

}

printf("\n");

return 0;
}

OUTPUT
Original array: 12 11 13 5 6
Sorted array: 5 6 11 12 13

COMPLEXITY
The complexity of Insertion Sort is determined by the nested loops, which dictate the
number of comparisons and shifts required.

1. Outer Loop: This loop iterates from the second element (index 1) to the end
of the array (n-1 times). In each iteration, it considers an element arr[i] to
be inserted into its correct position within the already sorted subarray
arr[0...i-1].
2. Inner Loop (while loop): This loop compares the key (the element to be
inserted) with elements in the sorted subarray (arr[j]) and shifts elements
that are greater than the key one position ahead.
○ Worst Case: The inner loop runs a maximum of i times for each
iteration of the outer loop. This occurs when the array is sorted in
reverse order, as every element needs to be compared with all
preceding elements and shifted.
○ Best Case: The inner loop runs a minimum of 1 time for each iteration
of the outer loop. This occurs when the array is already sorted, as the
key is compared only with the last element of the sorted subarray and
no shifts are needed.

Total Number of Comparisons and Shifts (Worst/Average Case):

In the worst case (reverse-sorted array), the outer loop runs n-1 times. For each i
from 1 to n-1, the inner loop runs i times. The total number of comparisons and
shifts is approximately:
1 + 2 + 3 + ... + (n-1)
15
This is an arithmetic series, and its sum is given by the formula: n * (n-1) / 2.
For large n, this simplifies to approximately n^2 / 2.
Therefore, both the worst-case and average-case time complexities are O(n^2), as
we discard constant factors and lower-order terms.

Best Case Complexity:

The best-case scenario occurs when the array is already sorted. In this situation, the
outer loop still runs n-1 times. However, for each iteration of the outer loop, the inner
while loop condition (arr[j] > key) will immediately be false (or only compare
once before being false), resulting in only one comparison (and no shifts) per outer
loop iteration.
This leads to a total of n-1 comparisons. Therefore, the best-case time complexity is
O(n).

Space Complexity:
Insertion Sort is an in-place sorting algorithm because it only requires a constant
amount of extra space for temporary variables (like key and j during the process).
Therefore, its space complexity is O(1).

16
 Experiment no.: - 5

SHELL SORT is an in-place comparison sort. It can be seen as either a

generalization of insertion sort or a diminishing increment sort. It improves upon
insertion sort by allowing the exchange of items that are far apart. The idea is to
arrange the elements in a way that allows them to move to their correct positions
more quickly than in a simple insertion sort. This is achieved by sorting elements that
are a certain 'gap' apart, then reducing the gap, and repeating the process until the
gap is 1 (which effectively becomes an insertion sort on the nearly sorted array).

INPUT CODE

#include <stdio.h>

void shell_sort(int arr[], int n) {

// Start with a large gap, then reduce the gap
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i += 1) {

int temp = arr[i];

int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
arr[j] = arr[j - gap];
arr[j] = temp;
}
}
}

int main() {
int arr[] = {12, 34, 54, 2, 3};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: \n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
shell_sort(arr, n);
printf("Sorted array: \n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}

OUTPUT

17
 Original array: 12 34 54 2 3
Sorted array: 2 3 12 34 54

COMPLEXITY

The complexity of Shell Sort is challenging to analyze precisely and depends heavily
on the chosen gap sequence. Unlike other sorting algorithms, there isn't a single
formula for its time complexity that holds true for all gap sequences. However, we
can discuss its performance in terms of general cases.

Key Idea Behind Complexity:

Shell Sort performs multiple passes of an "h-sorted" array, meaning elements

spaced 'h' positions apart are sorted. As the gap h decreases, the array becomes
more and more sorted. When the gap becomes 1, it essentially becomes an
Insertion Sort on a nearly sorted array, which is very efficient (O(n) best case for
Insertion Sort). The efficiency comes from elements moving larger distances in
earlier passes.

Time Complexity:

1. Worst Case: The worst-case time complexity of Shell Sort depends entirely
on the gap sequence used.
○ Using Hibbard's increments (1, 3, 7, ..., 2^k - 1), the worst-case
complexity is O(n^(3/2)).
○ Using Knuth's increments (1, 4, 13, ..., (3^k - 1)/2), the worst-case
complexity is O(n^(3/2)).
○ Some more advanced gap sequences can achieve O(n log^2 n) or
even O(n^(4/3)).
○ The worst-case for a poorly chosen gap sequence can still be O(n^2),
similar to Insertion Sort.
2. Average Case: The average-case complexity is also dependent on the gap
sequence. Generally, it's considered to be much better than O(n^2) but worse
than O(n log n). For common gap sequences like Hibbard's or Knuth's, it's
often close to O(n^(5/4)) or O(n^(7/6)).
3. Best Case: The best-case scenario also depends on the gap sequence and
the initial state of the array.
○ If the array is already sorted and the gap sequence includes 1 (which it
usually does as the final pass), the last pass (insertion sort with gap 1)
will take O(n) time. However, the preceding passes would still
contribute to the overall time.
○ Generally, for a nearly sorted array with a good gap sequence, the best
case can approach O(n log n), but it's often still considered higher,
such as O(n^(4/3)) for some sequences.

Summary of Time Complexity (Gap-Sequence Dependent):

18
Gap Sequence Worst Case Average Case

Hibbard's O(n^(3/2)) O(n^(5/4))

Knuth's O(n^(3/2)) O(n^(7/6))

Sedgewick's O(n^(4/3)) O(n^(7/6))

Generic/Poor O(n^2) O(n^2) Space Complexity:

Shell Sort is an in-place sorting algorithm. It only requires a constant amount of

extra space for a few temporary variables (like gap, i, j, temp). It does not use any
auxiliary data structures whose size grows with the input size.

Therefore, the space complexity is O(1).

19
 Experiment no.: - 6

Quick Sort is also a divide-and-conquer algorithm. It picks an element as a pivot

and partitions the given array around the picked pivot. There are many different
versions of quick sort that pick pivot in different ways.

1. Always pick the first element as pivot.

2. Always pick the last element as pivot (implemented below).
3. Pick a random element as pivot.
4. Pick median as pivot.

The key process in Quick Sort is partition(). The goal of partition() is to

arrange the array such that all elements smaller than the pivot come before the pivot,
and all elements greater than the pivot come after it.

INPUT CODE

#include <stdio.h>

// Function to swap two elements

void swap(int* a, int* b) {

int t = *a;
*a = *b;
*b = t;
}

int partition (int arr[], int low, int high) {

int pivot = arr[high]; // pivot

int i = (low - 1); // Index of smaller element

for (int j = low; j <= high - 1; j++) {

if (arr[j] < pivot) {

i++; // increment index of smaller element

swap(&arr[i], &arr[j]);
}
}

swap(&arr[i + 1], &arr[high]);

return (i + 1);

20
void quick_sort(int arr[], int low, int high) {

if (low < high) {

int pi = partition(arr, low, high);

quick_sort(arr, low, pi - 1);

quick_sort(arr, pi + 1, high);
}
}

int main() {

int arr[] = {10, 7, 8, 9, 1, 5};

int n = sizeof(arr) / sizeof(arr[0]);

printf("Original array: \n");

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

printf("%d ", arr[i]);

}

printf("\n");

quick_sort(arr, 0, n - 1);

printf("Sorted array: \n");

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

printf("%d ", arr[i]);

}

printf("\n");

return 0;

OUTPUT
Original array: 12 11 13 5 6
Sorted array: 5 6 11 12 13

COMPLEXITY
21
The complexity of Quick Sort is derived from its recursive, divide-and-conquer
approach, similar to Merge Sort. However, its performance varies significantly based
on the pivot selection strategy.

Understanding the Recurrence Relation

Quick Sort can be described by the following recurrence relation:

T(n) = T(k) + T(n-k-1) + O(n)

Where:

● T(n) is the time complexity to sort an array of size n.

● T(k) is the time taken to recursively sort the subarray of elements smaller than
the pivot (size k).
● T(n-k-1) is the time taken to recursively sort the subarray of elements greater
than the pivot (size n-k-1).
● O(n) represents the time taken to partition the array around the pivot.

Partition Operation Complexity

The partition function takes an array, a low index, and a high index, and
rearranges the elements such that all elements smaller than the pivot are to its left,
and all elements greater are to its right.

● It iterates through the array from low to high-1.

● In each iteration, it performs a comparison and potentially a swap.
● The number of comparisons and swaps is proportional to n (the size of the
subarray being partitioned).
● Therefore, the time complexity of the partition operation is O(n).

Worst Case Complexity: O(n^2)

The worst-case scenario for Quick Sort occurs when the pivot selection consistently
results in highly unbalanced partitions. This happens when the pivot is always the
smallest or largest element in the subarray.

● If the pivot is always the smallest element, k would be 0, and the recurrence
relation becomes:
T(n) = T(0) + T(n-1) + O(n) which simplifies to T(n) = T(n-1) + O(n)
● If the pivot is always the largest element, k would be n-1, and the recurrence
relation becomes:
T(n) = T(n-1) + T(0) + O(n) which also simplifies to T(n) = T(n-1) + O(n)

Expanding this recurrence:

T(n) = T(n-1) + O(n)
T(n) = T(n-2) + O(n-1) + O(n)
...
T(n) = T(1) + O(2) + ... + O(n-1) + O(n)
22
The sum of O(i) for i from 1 to n is approximately O(n^2). Therefore, the worst-case
time complexity of Quick Sort is O(n^2). This usually happens when the array is
already sorted or reverse-sorted and the pivot is chosen as the first or last element.

Best and Average Case Complexity: O(n log n)

The best and average-case scenarios for Quick Sort occur when the pivot selection
results in balanced partitions, dividing the array into two roughly equal halves. This
happens when the pivot is close to the median element.

● If the pivot consistently divides the array into two halves of roughly equal size
(e.g., k = n/2), the recurrence relation becomes:
T(n) = 2T(n/2) + O(n)

This recurrence relation is identical to that of Merge Sort. Using the Master Theorem
(Case 2, as derived for Merge Sort), where a=2, b=2, and f(n)=O(n), we compare
f(n) with n^(log_b a) = n^(log_2 2) = n^1. Since f(n) is proportional to
n^1, the solution is T(n) = O(n log n).

Space Complexity:
● Worst Case: O(n) - In the worst-case scenario (unbalanced partitions), the
recursive calls can form a linear chain, leading to a call stack depth
proportional to n.
● Average Case: O(log n) - In the average case (balanced partitions), the
recursive call stack depth is proportional to log n.

Conclusion
● Time Complexity:
○ Worst Case: O(n^2) - Occurs with poor pivot selection (e.g., already
sorted array with first/last element pivot).
○ Average Case: O(n log n) - Occurs with good pivot selection that
leads to balanced partitions.
○ Best Case: O(n log n) - Occurs when the pivot always divides the
array into two equal halves.
● Space Complexity:
○ Worst Case: O(n) (due to recursion stack)
○ Average Case: O(log n) (due to recursion stack)

23
 Experiment no.: - 7

MERGE SORT is a divide-and-conquer algorithm. It divides the unsorted list into n

sublists, each containing one element (a list of one element is considered sorted).
Then, it repeatedly merges sublists to produce new sorted sublists until there is only
one sublist remaining. This final sublist will be the sorted list.

INPUT CODE
#include <stdio.h>

#include <stdlib.h> // For malloc

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

int i, j, k;

int n1 = m - l + 1;

int n2 = r - m; // Create temporary 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]// Merge the temp arrays
back into arr[l..r]// Merge the temp arrays back into arr[l..r]// Merge
the temp arrays back into arr[l..r]// Merge the temp arrays back into
arr[l..r]// Merge the temp arrays back into arr[l..r]// Merge the temp
arrays back into arr[l..r]// 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 {

24
 arr[k] = R[j];

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

void merge_sort(int arr[], int l, int r) {

if (l < r) {
int m = l + (r - l) / 2;
merge_sort(arr, l, m);
merge_sort(arr, m + 1, r);
merge(arr, l, m, r);
}
}

int main() {

int arr[] = {38, 27, 43, 3, 9, 82, 10};

int n = sizeof(arr) / sizeof(arr[0]);

printf("Original array: \n");

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

printf("%d ", arr[i]);

}

printf("\n");
merge_sort(arr, 0, n - 1);
printf("Sorted array: \n");

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

printf("%d ", arr[i]);
}
printf("\n");

25
 return 0;

OUTPUT
Original array: 12 11 13 5 6
Sorted array: 5 6 11 12 13

COMPLEXITY
The complexity of Merge Sort is derived from its recursive, divide-and-conquer
nature. Let's analyze it by breaking down its two main phases: Divide and Conquer
(Merge).

Understanding the Recurrence Relation

Merge Sort can be described by the following recurrence relation:

T(n) = 2T(n/2) + O(n)

Where:

● T(n) is the time complexity to sort an array of size n.

● 2T(n/2) represents the time taken to recursively sort the two halves of the
array. The array is divided into two sub-arrays of size n/2.
● O(n) represents the time taken to merge the two sorted halves back into a
single sorted array.

Step-by-Step Derivation
Let's break down the O(n) merge operation and then solve the recurrence relation.

Merge Operation Complexity

The merge function takes two sorted subarrays and merges them into a single
sorted array.

● It iterates through both subarrays, comparing elements and placing them into
the temporary array or back into the original array.
● In the worst case, each element from both subarrays will be looked at and
moved exactly once.
● If we have two subarrays of size n/2 each, the total number of comparisons
and movements will be proportional to n/2 + n/2 = n.
● Therefore, the time complexity of the merge operation is O(n).

Solving the Recurrence Relation using the Master Theorem

The Master Theorem is a powerful tool to solve recurrence relations of the form
26
 T(n) = aT(n/b) + f(n).
For Merge Sort, we have:

● a = 2 (The number of subproblems)

● b = 2 (The factor by which the input size is divided)
● f(n) = O(n) (The cost of dividing the problem and combining the solutions,
which is the merge operation)

Now, we compare f(n) with n^(log_b a).

Here, log_b a = log_2 2 = 1.
So, we compare f(n) = O(n) with n^1 = n.

Since f(n) is proportional to n^(log_b a) (i.e., O(n) is Theta(n^1)), we fall into

Case 2 of the Master Theorem.

Case 2 of Master Theorem states:

If f(n) = Theta(n^(log_b a) * log^k n) for some constant k >= 0, then
T(n) = Theta(n^(log_b a) * log^(k+1) n).

In our case, f(n) = O(n) which means k=0 if we express n as n * log^0 n.

Therefore, applying Case 2:

T(n) = Theta(n^1 * log^(0+1) n)
T(n) = Theta(n log n)

Conclusion
● Time Complexity:
○ Worst Case: O(n log n) - Merge Sort always performs n log n
comparisons in the worst case because it always divides the array into
two halves and then merges them, regardless of the initial order.
○ Average Case: O(n log n) - Similar to the worst case, the division and
merging steps maintain this complexity.
○ Best Case: O(n log n) - Even if the array is already sorted, Merge Sort
will still perform the divide and merge operations, leading to O(n log
n) comparisons.
● Space Complexity: O(n) - Merge Sort requires auxiliary space for the
merging process. In the typical implementation, temporary arrays are created
to hold the sub-arrays during the merge operation. In the worst case, these
temporary arrays can take up O(n) space.

27
 Experiment no.: - 8
Objective:
To write programs to find the Minimum Spanning Tree (MST) of a connected,
weighted, undirected graph using
1. Kruskal’s Algorithm

2. Prim’s Algorithm.

Definition:
A Minimum Spanning Tree (MST) of a connected, weighted, undirected graph
is a subset of its edges that:

1. Connects all the vertices together (so the graph remains connected),
2. Contains no cycles (it is a tree), and
3. Has the minimum possible total edge weight among all the spanning trees of
the graph.

Two popular algorithms to find MST:

1. Kruskal’s Algorithm – Greedy approach; adds edges in increasing order of
weight, avoiding cycles.

2. Prim’s Algorithm – Starts with one vertex and grows the tree by adding the
smallest edge connecting the tree to a new vertex.

28
Kruskal’s Algorithm for Minimum Spanning Tree

Kruskal’s Algorithm is a greedy algorithm used to find the Minimum Spanning

Tree (MST) of a connected, weighted, undirected graph.
It builds the MST by selecting edges in increasing order of weight, making sure
that no cycles are formed.

Steps of Kruskal’s Algorithm

1. List all edges of the graph along with their weights.
2. Sort all the edges in non-decreasing order (from smallest to largest weight).
3. Initialize an empty set for the MST.
4. Repeat until there are 𝑉 − 1edges in the MST (where 𝑉is the number of vertices):
o Pick the smallest edge that does not form a cycle with the edges already
in the MST.
o Add this edge to the MST.
5. When you have 𝑉 − 1edges, the MST is complete.

Examples:
Construct a minimum spanning tree using kruskal’s algorithm for the graph given
below –

[Link] the first step, sort all the edges in the given graph in an ascending
order and store the values in an array.

EDGE COST EDGE COST

B→D 5 G→F 12
A→B 6 A→G 15
C→F 9 C→D 17
F→E 10 D→E 22
B→C 11 D→E 25

29
[Link], construct a forest of the given graph on a single plane.

[Link] the list of sorted edge costs, select the least cost edge and add it onto the
forest in output graph.
o B→D=5
o Minimum cost = 5
o Visited array, v = {B, D}

[Link], the next least cost edge is B → A = 6; so we add it onto the output
graph.
o Minimum cost = 5 + 6 = 11
o Visited array, v = {B, D, A}

30
[Link] next least cost edge is C → F = 9; add it onto the output graph.
o Minimum Cost = 5 + 6 + 9 = 20
o Visited array, v = {B, D, A, C, F}

[Link] next edge to be added onto the output graph is F → E = 10.

o Minimum Cost = 5 + 6 + 9 + 10 = 30
o Visited array, v = {B, D, A, C, F, E}

[Link] next edge from the least cost array is B → C = 11, hence we add it in the
output graph.
o Minimum cost = 5 + 6 + 9 + 10 + 11 = 41
o Visited array, v = {B, D, A, C, F, E}

31
8. The last edge from the least cost array to be added in the output graph is F → G =
12.
o Minimum cost = 5 + 6 + 9 + 10 + 11 + 12 = 53
o Visited array, v = {B, D, A, C, F, E, G}

 The obtained result is the minimum spanning tree of the given graph with cost
= 53.

Time Complexity
 Sorting edges: 𝑂(𝐸log 𝐸)
 Union-Find operations: 𝑂(𝐸log 𝑉)
 Overall: 𝑂(𝐸log 𝑉)

32
 Applications
 Designing least-cost networks (telecommunication, roads, electrical wiring)
 Clustering algorithms in machine learning
 Network optimization problems

 Prim’s Algorithm for Minimum Spanning Tree

Prim’s Algorithm is a greedy algorithm that finds a Minimum Spanning

Tree (MST) for a connected, weighted, undirected graph.
It builds the MST one vertex at a time, always choosing the minimum- weight
edge that connects a vertex in the tree to a vertex outside it.

Steps of Prim’s Algorithm

1. Start with any vertex (say, vertex A).
2. Mark this vertex as part of the MST.
3. From all the edges that connect the MST to vertices not yet in it, select the
smallest edge.
4. Add this edge and the connected vertex to the MST.
5. Repeat Step 3 until all vertices are included.

Example:
Find the minimum spanning tree using prims method (greedy approach) for
the graph given below with S as the arbitrary root.

Step 1:
Create a visited array to store all the visited vertices into it.
o V={}
The arbitrary root is mentioned to be S, so among all the edges that are
connected to S we need to find the least cost edge.
33
 o S→B=8
o V = {S, B}

Step 2:
Since B is the last visited, check for the least cost edge that is connected to the
vertex B.
o B→A=9
o B → C = 16
o B → E = 14
Hence, B → A is the edge added to the spanning tree.
o V = {S, B, A}

Step 3:
Since A is the last visited, check for the least cost edge that is connected to the
vertex A.
o A → C = 22
o A→B=9
o A → E = 11
But A → B is already in the spanning tree, check for the next least cost edge.
Hence, A → E is added to the spanning tree.

34
 o V = {S, B, A, E}

Step 4:
Since E is the last visited, check for the least cost edge that is connected to the
vertex E.
o E → C = 18
o E→D=3
Therefore, E → D is added to the spanning tree.
o V = {S, B, A, E, D}

Step 5:
Since D is the last visited, check for the least cost edge that is connected to
the vertex D.
o D → C = 15
o E→D=3
35
Therefore, D → C is added to the spanning tree.
o V = {S, B, A, E, D, C}

 The minimum spanning tree is obtained with the minimum cost = 46

Conclusion
 The MST connects all vertices with minimum total edge weight.
 Kruskal’s and Prim’s algorithms are both efficient and widely used in
network design, road mapping, and circuit layout Problems.

36