KEMBAR78
Merge Sort | PDF | Computer Science | Mathematical Logic
Scribd
Upload
11 views13 pages

Merge Sort

Merge Sort is a fast sorting algorithm that uses the divide and conquer approach to sort an array by recursively dividing it into halves and merging the sorted halves. The document outlines the definition, steps, algorithm, and a sample program for implementing Merge Sort. Additionally, it highlights applications such as sorting large data sets and external sorting.

Uploaded by

Ellendula Dheeraj
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 views13 pages

Merge Sort

Merge Sort is a fast sorting algorithm that uses the divide and conquer approach to sort an array by recursively dividing it into halves and merging the sorted halves. The document outlines the definition, steps, algorithm, and a sample program for implementing Merge Sort. Additionally, it highlights applications such as sorting large data sets and external sorting.

Uploaded by

Ellendula Dheeraj
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/ 13

MERGE SORT

AAT(Tech talk)
Name-E.Dheeraj
Branch-CSE(AIML)-A
Roll no-22951A6627
Topics to be covered:

■ Introduction
■ Definition
■ Steps involved
■ Algorithm
■ Program
■ Applications
Introduction:

■ Merge Sort is a complex and fast sorting algorithm that


repeatedly divides an un- sorted section into two equal
sub- sections, sorts them separately and
merges them correctly.
Definition:

■ Merge sort is a DIVIDE AND CONQUER algorithm. It divides


input array in two halves, calls itself for the two halves
and then merges the two sorted halves. The merge()
function is used for merging two halves.
Steps involved:

■ Divide the problem into sub-problems that are similar to


the original but smaller in size.
■ Conquer the sub-problems by solving them recursively. If
they are small enough, just solve them in a
straightforward manner.
■ Combine the solutions to create a solution to the
original problem.
Algorithm:

MergeSort(arr[], I, r)
If l< r
1. Find the middle point to divide the array into two halves:
middle m = (l + r) / 2
2. Call mergeSort for first half: Call mergeSort(arr, I, 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)
Example:
Program:
def mergeSort(arr):
if len(arr) > 1:
# Finding the mid of the array
mid = len(arr)//2
# Dividing the array elements
L = arr[:mid]
# Into 2 halves
R = arr[mid:]
# Sorting the first half
mergeSort(L)
# Sorting the second half
mergeSort(R)
i=j=k=0
# Copy data to temp arrays L[] and R[]
while i < len(L) and j < len(R):
if L[i] <= R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
# Checking if any element was left
while i < len(L):
arr[k] = L[i]
i += 1
k += 1
while j < len(R):
arr[k] = R[j]
j += 1
k += 1
# Code to print the list
def printList(arr):
for i in range(len(arr)):
print(arr[i], end=" ")
print()
# Driver Code
arr = [12,45,65,27,15]
print("Given array is")
printList(arr)
mergeSort(arr)
print("\nSorted array is ")
printList(arr)

Output:
Given array is
12 45 65 27 15

Sorted array is
12 15 27 45 65
Applications:

■ Merge sort type algorithms allows large data sets to be


sorted easily.
■ Merge sort accesses data sequentially and the need of
random access is low.
■ Inversion count problem.
■ Used in External Sorting.
THANK YOU..

You might also like