[go: up one dir, main page]
Scribd
Upload
21 views15 pages

Merge Sort

Merge sort is a divide and conquer algorithm that works by recursively splitting an array into halves and then merging the sorted halves. It has a time complexity of O(n log n) in all cases as it always divides the array into two halves and takes linear time to merge. While it requires additional space of O(n) for a temporary array, it can sort linked lists without using additional space and is particularly suited for sorting large datasets due to its guaranteed worst-case performance.

Uploaded by

Ahmadnur Jul
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
21 views15 pages

Merge Sort

Merge sort is a divide and conquer algorithm that works by recursively splitting an array into halves and then merging the sorted halves. It has a time complexity of O(n log n) in all cases as it always divides the array into two halves and takes linear time to merge. While it requires additional space of O(n) for a temporary array, it can sort linked lists without using additional space and is particularly suited for sorting large datasets due to its guaranteed worst-case performance.

Uploaded by

Ahmadnur Jul
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/ 15

20 November 2023 CS 103 (Data Structure and

Algorithm LEC)

Merge Sort
Brief Description
Notification

What is Merge Sort?


1
Divide and Conquer algorithm
• Breaks down multiple problems
recursively until they become
easier to solve
• Solutions are combined to solve
original problem

2
Stable sorting algorithm Merge Sort
• A stable sorting algorithm preserves the
original order of equivalent elements in the
sorted output. In other words, if two
identical values appear in the unsorted input,
they'll maintain their relative order in the
sorted result.
Complexity of The time complexity of Merge
Sort isθ(Nlog(N)) in all 3 cases
Merge Sort (worst, average, and best) as
merge sort always divides the
array into two halves and takes
linear time to merge two halves.

Time Complexity:

O(N log(N)) In case of merge sort, we need to


build a temporary array to merge
Space Complexity the sorted arrays. So the auxiliary
space requirement is O(N).
O(N)
Advantages and Disadvantages of using
Merge Sort

Advantages Disadvantages

• Merge sort can be used with • For small datasets, merge sort is
linked lists without taking up any slower than other sorting algorithms.
more space. • For the temporary array, mergesort
• A merge sort algorithm is used to requires an additional space of O(n).
count the number of inversions in • Even if the array is sorted, the merge
the list. sort goes through the entire process.
• Merge sort is employed in
external sorting.
• Sorting large datasets: Merge sort is particularly
Applications of well-suited for sorting large datasets due to its
Merge Sort guaranteed worst-case time complexity of O(n
log n).
• External sorting: Merge sort is commonly used
in external sorting, where the data to be sorted is
too large to fit into memory.
• Custom sorting: Merge sort can be adapted to
handle different input distributions, such as
partially sorted, nearly sorted, or completely
unsorted data.
General Principles of Merge Sort

Call Merge Sort on


each half to sort Merge both sorted
Split the
them recursively halves into a
array in half sorted array
5 2 8 1 6 4 7 3
5 2 8 1 6 4 7 3

5 2 8 1 6 4 7 3
5 2 8 1 6 4 7 3

5 2 8 1 6 4 7 3

5 2 8 1 6 4 7 3
5 2 8 1 6 4 7 3

5 2 8 1 6 4 7 3

5 2 8 1 6 4 7 3

5 2 8 1 6 4 7 3
5 2 8 1 6 4 7 3

2 5 1 8 4 6 3 7
5 2 8 1 6 4 7 3

2 5 1 8 4 6 3 7

1 2 5 8 3 4 6 7
5 2 8 1 6 4 7 3

2 5 1 8 4 6 3 7

1 2 5 8 3 4 6 7

1 2 3 4 5 6 7 8

You might also like