[go: up one dir, main page]
Scribd
Upload
10 views17 pages

Daa Presentation 1

Merge sort is a divide-and-conquer sorting algorithm that recursively divides an array into smaller subarrays, sorts them, and merges them back together. It has a time complexity of O(n log n) in the best, average, and worst cases, and requires O(n) auxiliary space. The algorithm is stable and efficiently handles sorted and reverse-ordered arrays.

Uploaded by

Falak Ayaz
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
10 views17 pages

Daa Presentation 1

Merge sort is a divide-and-conquer sorting algorithm that recursively divides an array into smaller subarrays, sorts them, and merges them back together. It has a time complexity of O(n log n) in the best, average, and worst cases, and requires O(n) auxiliary space. The algorithm is stable and efficiently handles sorted and reverse-ordered arrays.

Uploaded by

Falak Ayaz
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/ 17

PRESENTATION NO 1

DATA STRUCTURE AND ALGORITHM

SUBMITTED BY : FALAK AYAZ


Merge Sort – Data Structure and Algorithms

Merge sort is a sorting algorithm that follows the


divide-and-conquer approach. It works by recursively dividing the
input array into smaller subarrays and sorting those subarrays then
merging them back together to obtain the sorted array.
In simple terms, we can say that the process of merge sort is to
divide the array into two halves, sort each half, and then merge the
sorted halves back together. This process is repeated until the entire array
is sorted.
How does Merge Sort work?
Merge sort is a popular sorting algorithm known for its efficiency and
stability. It follows the divide-and-conquer approach to sort a given
array of elements.
Here’s a step-by-step explanation of how merge sort works:

1. Divide: Divide the list or array recursively into two halves until it
can no more be divided.
2. Conquer: Each subarray is sorted individually using the merge
sort algorithm.
3. Merge: The sorted subarrays are merged back together in sorted
order. The process continues until all elements from both
subarrays have
Illustration of Merge Sort:
Let’s sort the array or list [38, 27, 43, 10] using Merge Sort
Divide:

● [38, 27, 43, 10] is divided into [38, 27 ] and [43, 10] .
● [38, 27] is divided into [38] and [27] .
● [43, 10] is divided into [43] and [10] .

Conquer:

● [38] is already sorted.


● [27] is already sorted.
● [43] is already sorted.
● [10] is already sorted.
Merge:

● Merge [38] and [27] to get [27, 38] .


● Merge [43] and [10] to get [10,43] .
● Merge [27, 38] and [10,43] to get the final sorted list [10, 27,
38, 43]

Therefore, the sorted list is [10, 27, 38, 43] .


1: Complexity Analysis of Merge Sort:
● Time Complexity:
○ Best Case: O(n log n), When the array is already sorted or nearly
sorted.
○ Average Case: O(n log n), When the array is randomly ordered.
○ Worst Case: O(n log n), When the array is sorted in reverse order.
● Auxiliary Space: O(n), Additional space is required for the temporary array
used during merging.
Average complexity: n*log(n)

Best complexity: n*log(n)

Worst-case complexity: n*log(n)

Class: Comparison sort

Stable: Yes
2. Space Complexity

Space Complexity O(n)

Stable YES

○ The space complexity of merge sort is O(n). It is because, in


merge sort, an extra variable is required for swapping.
Example of Best Case:
Input Array (Already Sorted):

[1,2,3,4,5]

Example of Worst Case:


Input Array (Reversed Order):

[5,4,3,2,1]
Key Differences Between Best Case and Worst Case:

Case Best Case (Sorted Array) Worst Case (Reversed Array)

Input Array [1, 2, 3, 4, 5] [5, 4, 3, 2, 1]

Split Step Array is split into halves Array is split into halves recursively.
recursively.

Merge Step No elements need to be Every element is compared and


reordered, just compared. reordered.

Time O(n log n) O(n log n)


Complexity

Key Comparisons are still made Every comparison leads to a swap,


Observation during merging, but no swaps are and elements need to be placed in
required. correct order.
Conclusion:
● Best Case: The input array is already sorted (no reordering), but the
algorithm still follows the standard O(nlog⁡n)O(n \log n)O(nlogn) time
complexity.
● Worst Case: The input array is in reverse order, requiring more
reordering during the merge steps, but the time complexity remains
O(nlog⁡n)O(n \log n)O(nlogn), as it still follows the same splitting and
merging process.

You might also like