Merge Sort

1. Introduction

1.1. How does Merge Sort work?

Merge Sort is a popular sorting algorithm known for its efficiency and stablility. It follows the divide-and-conquer approach to sort a given array of elements.

1. Divide: Keep splitting the list into 2 parts until you have just one item in each part.
2. Conquer: Sort each of these tiny pieces individually by using the merge sort method.
3. Merge: Combine the pieces back together carefully so that they stay in order until you have one completely sorted list.

1.2. Illustration of Merge Sort

let's sort the array or list [38, 27, 43, 10] using Merge Sort.



Divide the array into 2 equal parts



Divide the subArrays into 2 parts



Combine individual items into a sorted group



Put together the sorted groups into one sorted list

1.3. Explanation

Divide:

• [38, 27, 43, 10] is divided into [38, 27] and [43, 10].
• [38, 27] is divided into [38] and [27].
• [43, 10] is divided into [43] and [10].

Conquer:

• [38] is already sorted.
• [27] is already sorted.
• [43] is already sorted.
• [10] is already sorted.

Merge:

• Merge [38] and [27] to get [27, 38].
• Merge [43] and [10] to get [10, 43].
• Merge [27, 38] and [10, 43] to get the final sorted list [10, 27, 38, 43].

Therefore, the sorted list is [10, 27, 38, 43].

2. Code

Output:

3. Kết Luận

References

• https://en.wikipedia.org/wiki/Merge_sort
• https://www.geeksforgeeks.org/merge-sort/