Scribd
Upload
Sign up
20 views5 pages

Recursive Merge Sort Explained

Recursion is a process where a function calls itself. Merge sort uses recursion to sort an array by recursively dividing it into halves and merging the sorted halves. Mathematical induction is used to prove theorems about sequences and iterative patterns by establishing a base case and inductive step.

Uploaded by

Sharafat Karim
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
20 views5 pages

Recursive Merge Sort Explained

Recursion is a process where a function calls itself. Merge sort uses recursion to sort an array by recursively dividing it into halves and merging the sorted halves. Mathematical induction is used to prove theorems about sequences and iterative patterns by establishing a base case and inductive step.

Uploaded by

Sharafat Karim
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.

PATUAKHALI SCIENCE

AND TECHNOLOGY
UNIVERSITY
COURSE CODE CIT-121

SUBMITTED TO:
Prof. Dr. M. A. Masud
Department of Computer and Information Technology
Faculty of Computer Science and Engineering

SUBMITTED BY:
Md. Sharafat Karim
ID: 2102024,
Registration No: 10151
Faculty of Computer Science and Engineering

Second semester final examination


Topic: Induction and Recursion
Date:
Recursion
Recursion is the process where we can use the same object inside the same object. It makes
it easy to call a function from itself. It can be used to define sequences, sets and functions.
For example, we can consider the following function,

Here, we can expend it like,

In this way we can call the same function from itself to find the result of the sequence. With
recursion we can write graph and binary tree algorithms more efficiently. It is also vastly
used in dynamic programming.

The Merge Sort


Merge sort is an bottom to top approach of sorting an array with support of recursion. In a
merge sort, at first we try to split the list into 2 smaller parts. In this way we try to make
things even more smaller. Finally we compare and merge them together. And from the
bottom to top we try to merge the list. And this is why it is known as merge sort. So we have
to merge items. We can draw it like a binary tree in this way.

At first we will work with the bottom numbers. Here we will sort 8 and 2 into a new list.
Thus it will become 2, 8. Later we will compare it with 4. So we need to functions. One
function is to split the array into two smaller parts. And then we will use an another
function to merge them back altogether. Here’s the algorithm for merging two sorted array,

Merging two lists

procedure merge(L1, L2 : sorted lists)


L := empty list
while L1 and L2 are both nonempty
remove smaller of first elements of L1 and L2 from its list; put it at the right end of L
if this removal makes one list empty then remove all elements from the other list
and append them to L
return L {L is the merged list with elements in increasing order}
After merging two lists, we will move to complete the algorithm with a recursive function
where we will call the same function again to divide our array into two smaller parts for our
calculation until we have only one element left in our hand.

The algorithm’s sudo-code is given below,

A Recursive Merge Sort.

procedure mergesort(L = a1 , ... , an )


if n > 1 then
m := ⌊n∕2⌋
L1 := a1 , a2, ... , am
L2 := am+1 , am+2, ... , an
L := merge(mergesort(L1), mergesort(L2))
{L is now sorted into elements in nondecreasing order}

On the above example if we run the merge sort after finding the sorted sub arrays we are
backtracking to the parent node. Then we are using the merge again and again to achieve
result. So in the worst case scenario we have to iterate through we have to check through
all of the values.

Time complexity
Time complexity of merge sort is n log(n). Here we are splitting the array into two parts like
binary search. So the number of comparison is O(n log(n)).

Here’s a c++ program to show the above merge sort algorithm,

#include <bits/stdc++.h>
using namespace std;

void print(int ar[], int n) {


for (int i=0; i <n; i++) {
cout << ar[i] << " ";
} cout << "\n";
}
int* merge(int *ar_1, int i, int *ar_2, int j) {
int p=0, p_1=0, p_2=0;
int* ar = (int *) malloc((i+j)*sizeof(int));
while (p_1 < i && p_2 < j) {
if (ar_1[p_1] < ar_2[p_2]) {
ar[p++] = ar_1[p_1++];
} else {
ar[p++] = ar_2[p_2++];
}
}
while (p_1 < i) {
ar[p++] = ar_1[p_1++];
} while (p_2 < j) {
ar[p++] = ar_2[p_2++];
}
return ar;
}

int* mergeSort(int *ar, int n) {


if (n == 1) return ar;
int i = n / 2, j = n - i;
int ar_1[i], ar_2[j];
for (int k=0; k < i; k++) {
ar_1[k] = ar[k];
} for (int k=i, l=0; k<n; k++) {
ar_2[l++] = ar[k];
}
return merge(mergeSort(ar_1, i), i, mergeSort(ar_2, j), j);
}

int main() {
int ar[] = {8, 2, 4, 6, 9, 7, 10, 1, 5, 3};
int* sorted = mergeSort(ar, sizeof(ar)/ sizeof(int));
print(sorted, sizeof(ar)/ sizeof(int));
}

Here the ar is a one dimensional array data structure. We use the merge sort algorithm on
this array. We are using pointers to pass as a reference and then using an another array to
copy it’s contents. And after sorting we are using malloc for dynamic programming to
create a permanent memory space and returning it’s location which is the final result.
Induction
Induction is the process of proving theorems of sequence summation of iterative patterns.

For example, let’s consider, P(n) is true for


n = b, b + 1, b + 2, ... ,
where b is an integer other than 1. We can use mathematical induction to accomplish this,
as long as we change the basis step by replacing P(1) with P(b).
In other words, to use mathematical induction to show that P(n) is true for
n = b, b + 1, b + 2, ... ,
where b is an integer other than 1, we show that P(b) is true in the basis step. In the
inductive step, we show that the conditional statement P(k) → P(k + 1) is true for k = b, b +
1, b + 2, … In this way we can prove that a certain equation is correct.

Here’s an example,
let’s consider a equation 1 + 2 + 22 + ⋯ + 2n = 2n+1 − 1.

Solution:
Let P(n) be the proposition that 1 + 2 + 22 + ⋯ + 2n = 2n+1 − 1 for the integer n.
P(0) is true because 20 = 1 = 21 − 1.
This completes the basis step.

For the inductive hypothesis,


we assume that P(k) is true for an arbitrary nonnegative integer k.
That is, we assume that
1 + 2 + 22 + ⋯ + 2k = 2k+1 − 1.
To carry out the inductive step using this assumption,
we must show that when we assume that P(k) is true,
then P(k + 1) is also true.
That is, we must show that
1 + 2 + 22 + ⋯ + 2k + 2k+1 = 2(k+1)+1 − 1 = 2k+2 − 1
assuming the inductive hypothesis P(k).
Under the assumption of P(k),
we see that
1 + 2 + 22 + ⋯ + 2k + 2k+1 = (1 + 2 + 22 + ⋯ + 2k ) + 2k+1
= (2k+1 − 1) + 2k+1
= 2 ⋅ 2k+1 − 1
= 2k+2 − 1.

So these two terms are same. So we can say that our induction process is working perfectly.

Common questions

Powered by AI

Merge sort and typical divide-and-conquer algorithms both involve recursively breaking down a problem into smaller sub-problems, solving each sub-problem, and then combining the solutions. In merge sort, the array is split into two halves recursively until each sub-array contains a single element. These are then merged in sorted order . The main contrast lies in the merging process, which is specific to sorting in merge sort, whereas other divide-and-conquer algorithms might use different means of combining solutions, such as accumulating results. The time complexity of merge sort, O(n log n), reflects the efficiency gained from this recursive division and merging .

Mathematical induction establishes the truth of propositions that hold for sequences by confirming a base case and using an inductive step . For instance, if a proposition P(b) is true for some integer b, and if assuming P(k) being true implies P(k+1) is true, then the proposition holds for all integers greater than or equal to b . This stepwise verification confirms the comprehensive correctness of equations involving sequences .

The O(n log n) time complexity of merge sort is important because it represents an efficient sorting method that can handle large datasets effectively . This complexity is due to the logarithmic number of levels created by dividing the array, each requiring linear time to merge, providing a significant advantage over less efficient sorting algorithms like bubble sort, which operates in O(n^2) time. Thus, ensuring performance scalability for larger inputs is crucial, making merge sort preferable in many sorting tasks .

The merge function in merge sort combines two sorted lists into a single sorted list. It repeatedly compares the smallest elements of each list, appending the smaller to the resulting list, and proceeds until all elements are merged into the resulting list . This systematic merging ensures that the final output is sorted, leveraging previously reduced problems into a complete and sorted dataset . It involves linear time complexity relative to the number of elements being merged .

Mathematical induction can be adapted by choosing any integer b as the base case instead of 1 . This involves proving that the proposition P(b) holds and then demonstrating that P(k) implies P(k+1) for all k ≥ b. This adaptation is significant because it allows more general application across problems that are not naturally starting at 1, thereby proving a broader class of propositions .

Recursion allows for more efficient graph and binary tree algorithm implementations by enabling a function to call itself until a base condition is met . In merge sort, recursion is crucial because it helps in dividing the array into increasingly smaller parts and then merging them back, which simplifies the sorting process . This approach leverages the divide-and-conquer strategy, allowing operations to be performed in smaller scopes with reduced complexity .

The divide and conquer strategy in merge sort works by recursively dividing an array into two halves until each half has a single element, which is by definition sorted . Each recursive call applies the same logic, processing smaller portions of the array independently. Once the base case is reached (arrays of single elements), these are merged in a sorted manner. The recursive backtracking effectively 'conquers' the original problem by combining these sorted sub-arrays back into a fully sorted array, efficiently managing time and resource utilization .

In merge sort, dynamic programming is indirectly used where memory allocation is handled dynamically. The algorithm implements dynamic memory allocation via `malloc` to manage arrays during sorting, allowing efficient use and storage of intermediate data . This dynamic memory management is crucial for creating and returning the merged arrays that result from recursive sorting and merging operations .

Recursion in merge sort typically increases space complexity due to the implicit stacking of function calls and additional memory allocation for new arrays or sub-problems at each recursion level . This layered memory usage is integral to divide and conquer, where arrays are copied and reallocated, augmenting the space overhead to O(n) beyond the data space for current recursive operations. Despite this, the trade-off with time complexity and sorting efficiency often justifies the added space complexity .

Recursion simplifies the manipulation and traversal of data structures like binary trees and graphs because operations can naturally reflect their hierarchical nature. Recursive functions can traverse nodes, process data, and backtrack efficiently without requiring explicit stack management . This inherently recursive property of trees and graphs aligns well with recursive functions that call themselves for new instances of sub-structures, simplifying implementation and improving code readability and maintenance .

You might also like