2 min read
Merge Sort Using Python
Last Update: 26 September, 2022Probably my favourite sorting algorithm and the one took the longestto Understand. I hope I can make it easier for you to grasp how does this algorithm work. We basically divide our array (or list) recursively until the pieces are small enough to sort. Finally we can start sorting them and start the "merging". Sounds really simple right? Let's get right to it!
§An Example to Help Us Understand
First of all I assume you understand the basic recursion. As we won't really do something complicated don't worry if you are not an expert at recursion.
Let's assume that we want to sort this array
arr = [42, 25, 37, 2, 11, 76, 12]
We are going to divide and start sorting / merging from the left side recursively. In the first step:
[42, 25, 37, 2] --- [11, 76, 12]
In the second step:
[42, 25] --- [37, 2] --- [11, 76, 12]
In the third step:
[42] --- [25] --- [37, 2] --- [11, 76, 12]
Now we can start sorting from the left side. Let's say we want to go from min to max in our array. First of all we will sort 42 and 25. So in the fourth step:
[25, 42] --- [37, 2] --- [11, 76, 12]
In the fifth step:
[25, 42] --- [37] --- [2] --- [11, 76, 12]
In the sixth step:
[25, 42] --- [2, 37] --- [11, 76, 12]
In the seventh step:
[2, 25, 37, 42] --- [11, 76, 12]
In the eighth step:
[2, 25, 37, 42] --- [11, 76] --- [12]
In the ninth episode:
[2, 25, 37, 42] --- [11] --- [76] --- [12]
In the tenth step:
[2, 25, 37, 42] --- [11, 76] --- [12]
In the eleventh step:
[2, 25, 37, 42] --- [11, 12, 76]
And finally in the twelfth step:
[2, 11, 12, 25, 37, 42, 76]
This algorithm helps us understand the importance of divide and conquer algorithms. We simply divide the problem into smaller pieces that are easier to solve.
The code for this algorithm actually looks like this:
def mergeSort(nums):
if len(nums) <= 1:
return nums
if len(nums) > 1:
mid = len(nums) // 2
left = nums[:mid]
right = nums[mid:]
mergeSort(left)
mergeSort(right)
i = 0
j = 0
k = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
nums[k] = left[i]
i += 1
else:
nums[k] = right[j]
j += 1
k += 1
while i < len(left):
nums[k] = left[i]
i += 1
k += 1
while j < len(right):
nums[k] = right[j]
j += 1
k += 1
numbers = [42, 25, 37, 2, 11, 76, 12]
mergeSort(numbers)
print(numbers)
§Complexity of Merge Sort
The time complexity for merge sort is O(nlogn) since we are dividing our array into two n times approximately. AS you can see merge sort may not be the fastest algorithm to sort relatively bigger arrays / lists. It's suggested that we use merge sort on relatively smaller linked lists.
Space complexity of merge sort is O(n). Creating all these subarrays to sort later was going to cost us of course. So if you are short on space maybe don't choose merge sort.
In terms of stability we can be sure that merge sort is stable. We use left < right to compare elements. In the case of equality we first copy the left value into our array and then the right one. Thus our order is preserved. This proves that merge sort is stable.
Keep on learning!
Ilker AkbiyikTable of Contents
Related Posts
