[go: up one dir, main page]
Scribd
Upload
33 views11 pages

Week13 Lecture 38

Merge sort is a sorting algorithm that runs in O(n log n) time in all cases. It divides an unsorted array into single element subarrays, repeatedly merges the subarrays to produce sorted subarrays, and finally combines them into a single sorted array. The key steps are to 1) divide the array into halves, 2) recursively sort the halves, and 3) merge the sorted halves back together.

Uploaded by

wardabibi69
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
33 views11 pages

Week13 Lecture 38

Merge sort is a sorting algorithm that runs in O(n log n) time in all cases. It divides an unsorted array into single element subarrays, repeatedly merges the subarrays to produce sorted subarrays, and finally combines them into a single sorted array. The key steps are to 1) divide the array into halves, 2) recursively sort the halves, and 3) merge the sorted halves back together.

Uploaded by

wardabibi69
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 11

Merge Sort

Sorting Algorithm
Week 13 – Lecture 38
Background
What is Recursion???

Selection Sort and Insertion Sort have a worst-case running time of O(n2).
As the size of input grows, insertion and selection sort can take a long
time to run. Merge sort, on the other hand, runs in O(n*log n) time in all
the cases.
Divide and Conquer
In Merge Sort, the given unsorted array with n elements is divided into n subarrays,
each having one element because a single element is always sorted in itself. Then, it
repeatedly merges these subarrays, to produce new sorted subarrays, and in the end,
one complete sorted array is produced.

The concept of Divide and Conquer involves three steps:

 Divide the problem into multiple small problems.


 Conquer the subproblems by solving them. The idea is to break down the problem
into atomic subproblems, where they are solved.
 Combine the solutions of the subproblems to find the solution to the actual
problem.
Divide and Conquer
How Merge Sort Works?
 In merge sort, we break the given array midway, for example if the original array
had 6 elements, then merge sort will break it down into two subarrays with 3
elements each.
 we will break these subarrays into even smaller subarrays, until we have multiple
subarrays with single element in them.
Example
Example (Cont.….)
Basic Steps
In merge sort, we follow the following steps:

1. We take a variable p and store the starting index of our array in this. And we take
another variable r and store the last index of the array in it.
2. Then we find the middle of the array using the formula (p + r)/2 mark the middle
index as q, and break the array into two subarrays, from p to q and from q + 1 to r
index.
3. Then we divide these 2 subarrays again, just like we divided our main array and
this continues.
4. Once we have divided the main array into subarrays with single elements, then we
start merging the subarrays.
Pseudocode
MergeSort (A, lb, ub)
{
If (lb <ub)
{
mid = (lb + ub)/2
mergesort ( A, lb, mid);
mergesort (A, mid+1, ub);
merge (A, lb, mid, ub);
}
}
Code for Merge
Merge (A, lb, mid, ub)
{
i = lb;
j = mid + 1;
k = lb;
while ( i < = mid && j <= ub)
{
if (a[i] <= a[j])
{
b[k] = a[i];
i++; k++;
}
else
{
b[k] = a[j];
j++; k++;
}
}
Code for Merge
if (i > mid)
{
while ( j <= ub)
{
b[k] = a[j]; j++; k++;
}
}
else {
while ( i<= mid)
{
b[k] = a[i];
i++;
k++;
}
}

You might also like