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!