Scribd
Upload
11 views10 pages

Merge Sort Analysis for CSE Students

Merge sort is an efficient sorting algorithm that works by recursively dividing an array into two halves, sorting each half, and then merging the sorted halves into a single sorted array. It has a time complexity of O(n log n) in all cases, making it independent of the initial array distribution. The document compares merge sort to other sorting algorithms like bubble sort, insertion sort, and selection sort, noting that merge sort has better worst-case time complexity than these other algorithms.

Uploaded by

Sheetu Jain
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
11 views10 pages

Merge Sort Analysis for CSE Students

Merge sort is an efficient sorting algorithm that works by recursively dividing an array into two halves, sorting each half, and then merging the sorted halves into a single sorted array. It has a time complexity of O(n log n) in all cases, making it independent of the initial array distribution. The document compares merge sort to other sorting algorithms like bubble sort, insertion sort, and selection sort, noting that merge sort has better worst-case time complexity than these other algorithms.

Uploaded by

Sheetu Jain
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

APEX INSTITUTE OF TECHNOLOGY

DEPARTMENT: CSE
Bachelor of Engineering (Computer Science & Engineering)
Data Structures and 20CST-231

ARRAYS DISCOVER . LEARN . EMPOWER


Sorting- Merge
Sort
Course Outcome
CO Title Level
Number

CO1 Understand
Understand the merge sort technique.

CO2 Analysis
Comparison with other sorting methods

2
Merge Sort
• Merge sort is one of the most efficient sorting algorithms.
• It works on the principle of Divide and Conquer.
• Merge sort repeatedly breaks down a list into several sublists until
each sublist consists of a single element and merging those sublists in
a manner that results into a sorted list.

3
Merge Sort
• In case of merge sort, array is recursively divided into two halves, then both arrays are sorted and
again sorted to make single sorted array.
Algorithm
MergeSort(arr[], l, r)
If r > l
1. Find the middle point to divide the array into two halves:
middle m = l+ (r-l)/2
2. Call mergeSort for first half:
Call mergeSort(arr, l, m)
3. Call mergeSort for second half:
Call mergeSort(arr, m+1, r)
4. Merge the two halves sorted in step 2 and 3:
Call merge(arr, l, m, r)

4
5
Merge Sort
MS(a,0,6)

Mid=3,Beg=0, End=6

MS(a,0,3) MS(a,4,6) MSS(a,0,3,4,6)

Mid=1,Beg=0, End=3 Mid=5,Beg=4, End=6 6

MS(a,0,1) MS(a,2,3) MSS(a,0,1,2,3) MS(a,4,5) MS(a,6,6) MSS(a,4,5,6,6)


Mid=0,Beg=0, End=1 Mid=2,Beg=2, End=3 If(6<6)
Mid=4,Beg=4, End=5 5
3
MS(a,0,0) MS(a,1,1) MSS(a,0,0,1,1) MS(a,4,4) MS(a,5,5) MSS(a,4,4,5,5)
If(0<0) If(1<1) 1 If(4<4) If(5<5)
4
MS(a,2,2) MS(a,3,3) MSS(a,2,2,3,3)
If(2<2) If(3<3) 2
6
Complexity Analysis – Merge Sort
Time Complexity
As we have already learned in Binary Search that whenever we divide a number into half in every step, it can be
represented using a logarithmic function, which is log n and the number of steps can be represented by log n + 1(at most)

Also, we perform a single step operation to find out the middle of any subarray, i.e. O(1).

And to merge the subarrays, made by dividing the original array of n elements, a running time of O(n) will be required.

Hence the total time for mergeSort function will become n(log n + 1), which gives us a time complexity of O(n*log n).

Worst Case Time Complexity [ Big-O ]: O(n*log n)

Best Case Time Complexity [Big-omega]: O(n*log n)

Average Time Complexity [Big-theta]: O(n*log n)


Space Complexity
O(n)

7
Comparison of Sorting Methods Discussed
• Bubble sort and Insertion sort – 
Average and worst case time complexity: n^2 
Best case time complexity: n when array is already sorted. 
Worst case: when the array is reverse sorted. 
• Selection sort – 
Best, average and worst case time complexity: n^2 which is independent
of distribution of data. 
 
• Merge sort – 
Best, average and worst case time complexity: nlogn which is independent
of distribution of data. 
8
REFERENCES
• “Data Structures and Algorithms Made Easy: Data Structures and Algorithmic Puzzles” by Narasimha
Karumanchi
• “Data Structures Using C” by Aaron M. Tenenbaum
• “Data Structures and Algorithms” by Alfred V. Aho
• [Link]

9
THANK YOU

For queries
Email: rajiv.e8509@[Link]

You might also like