Merge Sort

Sorting, Data Structures & Algorithms

Images from Canva

In my previous blog, we explored insertion sort, a method that, while functional, lacked efficiency. In this blog, let’s delve into a more effective sorting technique: merge sort.

Merge sort operates on the divide and conquer principle. As the name suggests, it involves three key steps: splitting, sorting, and merging. Here’s a closer look at each:

1. Splitting: This initial step involves dividing the array into smaller subarrays recursively until each subarray contains only one or no elements.
2. Sorting: This step rearranges the elements within the subarrays into their correct order. If sorting in ascending order, smaller elements are positioned to the left while larger ones are placed to the right.
3. Merging: The final stage is to merge the sorted subarrays back together. At each stage of merging, sorting is performed to ensure that the elements are correctly ordered. This process continues from the bottom up until the entire array is sorted.

What makes merge sort particularly elegant is its ability to break down the complexity of the problem into simpler cases, using recursion. We’ll look deeper into the implementation details shortly, but for now, the diagram below is a visual representation of how this sorting mechanism works.