## DEV Community 👩‍💻👨‍💻 is a community of 917,994 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. Aya Bouchiha

Posted on • Updated on

# Merge sort algorithm

## Definition of the merge sort algorithm

merge sort is an efficient algorithm, and one of Divide and Conquer algorithms that splits the giving array into two halves, and then merge them in a sorted manner.

## Time complexity of merge sort

best-case average case worst-case
O(n log n) O(n log n) O(n log n)

## Space complexity

The space complexity of merge sort is O(n)

## Advantages of using merge sort algorithm

• Fast for large arrays unlike selection, insertion, and bubble sort it doesn't go through the whole array many times.

## Disadvantages of using merge sort algorithm

• extra space to store subarrays
• slow for small arrays
• the algorithm does the whole process even the array is already sorted

## Implementation of merge sort using python

``````def MergeSortAlgorithm(arr: list) -> list:
"""
[ name ] => merge sort
[ type ] => sorting algorithms
[ time complexity ] => O(n log n)
[ space complexity ] => O(n)
[ params ] => (
arr {list} list to sort
)
"""
n = len(arr)
if n > 1:
#getting the middle of the giving array
mid = n // 2
# left half
leftHalf  =  arr[:mid]
# right half
rightHalf =  arr[mid:]
# sort left half
MergeSortAlgorithm(leftHalf)
# sort right half
MergeSortAlgorithm(rightHalf)

i = k = j = 0

while i < len(leftHalf) and j < len(rightHalf):
if leftHalf[i] > rightHalf[j]:
arr[k] = rightHalf[j]
j+=1
else:
arr[k] = leftHalf[i]
i+=1
k+=1
# inserting to the sortedArray the rest of the leftHalf
while i < len(leftHalf):
arr[k] = leftHalf[i]
k += 1
i+=1
# inserting to the sortedArray the rest of the rightHalf
while j < len(rightHalf):
arr[k] = rightHalf[j]
k+=1
j+=1
``````

## References and useful resources

Thank you so much for your time! :)
#day_11