[go: up one dir, main page]
Scribd
Upload
6 views6 pages

1 Merge Sort

The document provides an overview of the Merge Sort algorithm, detailing its divide-and-conquer approach to sorting an array by recursively breaking it down and merging sorted subarrays. It includes the algorithm's implementation in Python, along with its time complexity analysis, which consistently shows O(n log n) for best, average, and worst cases. Additionally, it notes the auxiliary space requirement of O(n) for temporary arrays used during merging.

Uploaded by

gul.zaib2012
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views6 pages

1 Merge Sort

The document provides an overview of the Merge Sort algorithm, detailing its divide-and-conquer approach to sorting an array by recursively breaking it down and merging sorted subarrays. It includes the algorithm's implementation in Python, along with its time complexity analysis, which consistently shows O(n log n) for best, average, and worst cases. Additionally, it notes the auxiliary space requirement of O(n) for temporary arrays used during merging.

Uploaded by

gul.zaib2012
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 6

Superior University

Sargodha Campus

Advanced Algorithms
Assignment

Submitted to:

Dr. Naila Hamid

Submitted by:

Muhammad Arsalan

SU72-MSCSW-F24-004
Merge Sort
The Merge Sort algorithm is a divide-and-conquer algorithm that sorts an array by first breaking
it down into smaller arrays, and then building the array back together the correct way so that it
is sorted.

Divide: The algorithm starts with breaking up the array into smaller and smaller pieces until one
such sub-array only consists of one element.

Conquer: The algorithm merges the small pieces of the array back together by putting the
lowest values first, resulting in a sorted array.

The breaking down and building up of the array to sort the array is done recursively.

In the animation above, each time the bars are pushed down represents a recursive call,
splitting the array into smaller pieces. When the bars are lifted up, it means that two sub-arrays
have been merged together.

How it 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 been merged.
Algorithm
def mergeSort(arr):

if len(arr) <= 1:

return arr

mid = len(arr) // 2
leftHalf = arr[:mid]

rightHalf = arr[mid:]

sortedLeft = mergeSort(leftHalf)

sortedRight = mergeSort(rightHalf)

return merge(sortedLeft, sortedRight)

def merge(left, right):

result = []

i=j=0

while i < len(left) and j < len(right):

if left[i] < right[j]:

result.append(left[i])

i += 1

else:

result.append(right[j])

j += 1

result.extend(left[i:])

result.extend(right[j:])

return result
unsortedArr = [3, 7, 6, -10, 15, 23.5, 55, -13]

sortedArr = mergeSort(unsortedArr)

print("Sorted array:", sortedArr)

Merge Sort Time Complexity

The time complexity for Merge Sort is

O(n⋅logn)O(n⋅log⁡n)

And the time complexity is pretty much the same for different kinds of arrays. The algorithm
needs to split the array and merge it back together whether it is already sorted or completely
shuffled.

The image below shows the time complexity for Merge Sort.

Complexity Analysis of Merge Sort:


 Time Complexity:
o Best Case: O(n log n), When the array is already sorted or nearly sorted.
o Average Case: O(n log n), When the array is randomly ordered.
o 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.

Recursive function:
T(n)=2T(n/2) + An. We call this formula a recurrence relation for the running time of Merge Sort
algorithm. To analyze the running time, we need to solve the recurrence relation to get T(n) =
O(f(n)) where f(n) is one of the familiar functions like n2.

You might also like