DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
(Algorithm Design and Analysis)
(Merge sort)
Presentation by:
S. Rajendra
(22UJ1A6757)
III YEAR-ISEM.
Merge Sort
[Link]
Introduction to Merge Sort
Merge Sort is a divide-and-conquer
algorithm used for sorting arrays.
It was invented by John von Neumann
in 1945 and is efficient for large
datasets.
The algorithm works by recursively
splitting the array into smaller
subarrays until they can be easily
sorted.
How Merge Sort Works
The algorithm begins by dividing the
array into two halves.
Each half is then sorted recursively
using the same merge sort algorithm.
Once the two halves are sorted, they
are merged back together to form a
single sorted array.
Merge Process Explained
The merge process involves
comparing the smallest elements of
each subarray.
The smaller element is placed into a
new array, and this process continues
until one subarray is empty.
After one subarray is exhausted, the
remaining elements from the other
subarray are copied into the new
array.
Time Complexity of Merge Sort
Merge Sort has a time complexity of
O(n log n) in the best, average, and
worst cases.
This makes it more efficient than
simpler sorting algorithms like bubble
sort or insertion sort for large
datasets.
The log n factor comes from the
repeated halving of the array, while
the n factor comes from the merging
process.
Space Complexity of Merge Sort
The space complexity of Merge Sort is
O(n) due to the temporary arrays
used during the merge process.
This additional space requirement can
be a drawback in memory-constrained
environments.
However, it allows Merge Sort to
maintain stability, meaning equal
elements retain their relative
positions.
Applications of Merge Sort
Merge Sort is widely used in
applications where stability is
required, such as in database sorting.
It is also used in external sorting
algorithms where data is too large to
fit into memory.
Additionally, Merge Sort serves as a
foundation for other algorithms,
including TimSort, which is used in
Python's built-in sort functions.
This presentation provides a concise