Merge Sort
Merge Sort is an efficient sorting algorithm based on the Divide and Conquer technique. It repeatedly divides the given array into two equal halves until each sub-array contains only one element. These smaller arrays are then merged together in sorted order to obtain the final sorted array.
Unlike Bubble Sort and Selection Sort, Merge Sort performs sorting by dividing the problem into smaller parts and then combining the sorted results. Due to its predictable performance, it is widely used in database systems, external sorting and large-scale data processing.
Prerequisite
Before learning Merge Sort, students should understand the following concepts.
| Concept | Description |
|---|---|
| Arrays | Merge Sort is generally implemented on arrays. |
| Recursion | The algorithm repeatedly calls itself on smaller sub-arrays. |
| Divide and Conquer | Merge Sort follows the Divide and Conquer strategy. |
Working Principle
Merge Sort works in two important phases.
- Divide: Divide the array into two equal halves until each part contains only one element.
- Merge: Combine the smaller sorted arrays to produce a larger sorted array.
Illustration of Merge Sort
Example
Consider the following unsorted array.
38 27 43 10
Step 1 : Divide the array into two equal halves.
38 27
43 10
Step 2 : Divide each half until only one element remains.
38
27
43
10
Step 3 : Merge adjacent elements in sorted order.
27 38
10 43
Step 4 : Merge the two sorted arrays to obtain the final sorted array.
10 27 38 43