Get startedGet started for free

Merge sort

1. Merge sort

In this video, we will learn the merge sort algorithm.

2. Merge sort

Merge sort follows the divide and conquer strategy. This technique is divided into the following parts. Divide: this process divides the problem into smaller sub-problems. Conquer: the sub-problems are solved recursively. Combine: the solutions of the sub-problems are combined in order to achieve the final solution.

3. Merge sort - in action

Let's see how merge sort works. Suppose we want to order the following numbers by applying the merge sort algorithm. The algorithm

4. Merge sort - in action

divides the data recursively into two parts

5. Merge sort - in action

and keeps

6. Merge sort - in action

dividing

7. Merge sort - in action

until

8. Merge sort - in action

each list

9. Merge sort - in action

has

10. Merge sort - in action

one

11. Merge sort - in action

element. Then, we

12. Merge sort - in action

combine them

13. Merge sort - in action

by sorting them

14. Merge sort - in action

into another

15. Merge sort - in action

list.

16. Merge sort - implementation

Let's implement this algorithm in Python. We start by defining the base case. If the length of the list is equal to one, we will consider that the list is already sorted, and we will not continue. However, if the length of the list is greater than one, we will divide the list into two parts, the left_half and the right_half. Then, we call merge_sort recursively on both halves until each list has only one element, that is, the base case. Then, we proceed to merge the sorted parts. To do this, we start by declaring the i variable for the index of the left_half, the j variable for the index of the right_half, and the k variable for the index of the final list. We set all of them to zero. While the i variable is less than the length of the left_half and j is less than the length of the right_half, we compare if the left item is less than the right item. If it is, we copy this value to position k and increment i by one. However, if the left item is greater than the right item, the value to be included will be the right item, and j will be incremented by one. After these checks, we increment k by one. When we finish iterating over all the elements of one of the halves or both halves, we check if the left half has any remaining elements. If it does, we iterate over them and place them into the list. We do the same in case there are any remaining elements in the right half. As this is a recursive function, we will execute this merge process for every call to merge_sort. We can test this algorithm as shown.

17. Merge sort - complexity

Merge sort has a complexity of O of n log n. This is a significant improvement over bubble sort, selection sort, and insertion sort, which have a complexity of O of n-squared. O of n log n grows much slower than O of n-squared. Therefore, merge sort is suitable for sorting large lists of numbers. In average and best cases, it also has a complexity of n log n. Other algorithms like bubble sort or insertion sort have better best case complexity. The inconvenience of this algorithm is its space complexity. We haven't used this concept so far, but let's recall that space complexity is the extra memory space required by an algorithm. We aren't going to cover how to calculate it, but it is important to know that this algorithm needs extra space to treat the two halves, having a space complexity of O of n. By contrast, the other sorting algorithms that we already studied have a space complexity of O of one. There are other variants of merge sort that reduce this space complexity, but they are out of the scope of this course.

18. Let's practice!

Let's practice!