Scribd
Upload
81 views9 pages

Mergesort: 7/11/2019 Mitra Kabir, Dept. of CSE, DU 1

Mergesort is a sorting algorithm that uses a divide-and-conquer approach. It divides an array into halves, recursively sorts the halves, and then merges the sorted halves into a single sorted array. It maintains the steps of dividing, conquering by recursively sorting the subarrays, and merging the sorted subarrays. Mergesort runs in O(n log n) time as it makes log n passes over the array, with each pass requiring linear time to merge.

Uploaded by

Sadia Afreen
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
81 views9 pages

Mergesort: 7/11/2019 Mitra Kabir, Dept. of CSE, DU 1

Mergesort is a sorting algorithm that uses a divide-and-conquer approach. It divides an array into halves, recursively sorts the halves, and then merges the sorted halves into a single sorted array. It maintains the steps of dividing, conquering by recursively sorting the subarrays, and merging the sorted subarrays. Mergesort runs in O(n log n) time as it makes log n passes over the array, with each pass requiring linear time to merge.

Uploaded by

Sadia Afreen
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
You are on page 1/ 9

Mergesort

7/11/2019 Mitra Kabir, Dept. of CSE, DU 1


The Divide-and-Conquer Approach
 Two Necessary Steps
1. Divide: Smaller problems are solved recursively.

2. Conquer: The solution of the original problem is formed from the solutions
to the subproblems.
 The running time equation of divide and conquer approach:
T(n) = 2T(n/2) + O(n) where n is the input size.
The solution to this equation is O(nlog2n).

7/11/2019 Mitra Kabir, Dept. of CSE, DU 2


Merge Sort
• Merge sort is a comparison sorting technique.
• This technique follows the divide-and-conquer approach.
• It maintains the following 3 steps:
1. Divide: Divide N-element sequence to be sorted into two subsequences of
about N/2 elements each and sort the two subsequences recursively .

2. Conquer: Merge the two sorted subsequences to produce the sorted result.

• Merge sort uses the “merge” step to combine two sorted sublists to create one single
sorted list.
• Suppose A is a sorted list with R elements and B is another sorted list with S elements.
After merging there is only a single sorted list C with N=R+S elements.

7/11/2019 Mitra Kabir, Dept. of CSE, DU 3


Mergesort Algorithm

Merge-Sort(A, Left, Right) Merge(A, Left, Center, Right)

(1) If Left < Right do steps 2 to 5 (1) n1 = Center – Left + 1


(2) n2 = Right – Center
(2) Set Center = (Left+Right)/2
(3) Create arrays L[1…n1] and R[1…n2]
(3) Merge-Sort (A, Left, Center)
(4) For i = 1 to n1
(4) Merge-Sort (A,Center+1, Right)
(5) do L[i] = A[Left + i -1]
(5) Merge(A, Left, Center, Right) (6) For j = 1 to n2
(6) End (7) do R[j] = A[Center + j]
(8) i=1
(9) j=1
(10) For k = Left to Right
(11) do if L[i] <= R[j]
(12) then A[k] = L[i]
(13) i=i+1
(14) else A[k] = R[j]
(15) j=j+1
(16) End
7/11/2019 Mitra Kabir, Dept. of CSE, DU 4
Example:
Suppose Array A = 5, 2, 4, 7, 1, 3, 2, 6. Sort the array using Mergesort.

5 2 4 1 7 3 2 6

5 2 4 1 7 3 2 6

5 2 4 1 7 3 2 6

5 2 4 1 7 3 2 6

2 5 1 4 3 7 2 6

1 2 4 5 2 3 6 7

1 2 2 3 4 5 6 7

7/11/2019 Mitra Kabir, Dept. of CSE, DU 5


Example:
Suppose Array A = 38, 27, 43, 3, 9, 82 and 10. Sort the array using Mergesort.

7/11/2019 Mitra Kabir, Dept. of CSE, DU 6


Complexity of Merge-Sort
Let T(N) be the number of comparisons needed to sort N elements using merge
sort. This algorithm requires at most logN passes. Moreover, each pass merges
a total of N elements and each pass will require at most N comparisons. So, for
all cases, T(N) = 0(NlogN).

Recurrence Relation for Mergesort

T(1) = 1 For N = 1

T(N) = 2T(N/2) + N Otherwise

7/11/2019 Mitra Kabir, Dept. of CSE, DU 7


# T(N) = 2T(N/2) + N is equivalent to O(Nlog2N)

Solution:
T(N) = 2T(N/2) + N
T(N/2) = 2T(N/4) + N/2
T(N/4) = 2T(N/8) + N/4
……………………..
T(2) = 2T(1) + 2

T(N) = 2KT(N/2K) + K.N

By using 2K = N, it is obtained as
T(N) = NT(1) + NLog2N = N + NLog2N = O(NLog2N)

So, T(N) = 2T(N/2) + N is equivalent to O(Nlog2N).

7/11/2019 Mitra Kabir, Dept. of CSE, DU 8


END

7/11/2019 Mitra Kabir, Dept. of CSE, DU 9

You might also like