Example 3: Merge Sort

Previously in this course, we learned two sorting algorithms: selection sort and insertion sort. We have another sorting algorithm which is recursive in nature, and it is known as merge sort.

Introduction

A merge sort recursively breaks the values to be sorted in half until there is only one value to be sorted, and then it merges the sorted lists/arrays into one sorted list/array. Here’s a basic overview of the process:

Here, the numbers on arrows indicate the order in which steps proceed. Additionally, the green color means merging, and the red color means splitting the array into halves until the size becomes $1$ ...