🧠 What I Learned About Merge Sort Today

Sorting algorithms are a fundamental part of computer science, and today I focused on understanding Merge Sort — one of the most efficient and widely used sorting algorithms. In this blog post, I’m documenting what I’ve learned through both exploration and implementation.

---

🔍 What is Merge Sort?

Merge Sort is a divide and conquer algorithm. Instead of trying to sort the entire list at once, it works by repeatedly splitting the list into smaller sublists, sorting those, and then merging them back together.

---

✨ Key Steps in Merge Sort

1. Divide the list into two halves.

2. Recursively sort each half using merge sort.

3. Merge the two sorted halves into one sorted list.

This process continues until the entire list is sorted.

---

🧩 The Most Important Part: Merging

The merging step is where two sorted lists are combined into a single sorted list. This involves:

• Comparing the elements at the start of each list.

• Adding the smaller element to the result.

• Repeating the process until one of the lists is empty.

• Appending any remaining elements from the non-empty list.

This was the trickiest part for me to understand, but once I got the logic of comparing and appending leftovers, it became clear.

---

✅ My Final Merge Sort Implementation

Here’s the code I wrote after fully understanding how merge sort works:

def merge_sort(arr):
    n = len(arr)

    if len(arr) <= 1:
        return arr
    else:
        mid = len(arr) // 2
        right_half = arr[mid:]
        left_half = arr[:mid]

        left_half = merge_sort(left_half)
        right_half = merge_sort(right_half)

        final_arr = []

        i = 0
        j = 0

        while i < len(left_half) and j <len(right_half):
            if left_half[i] < right_half[j]:
                final_arr.append(left_half[i])
                i += 1
            else:
                final_arr.append(right_half[i])
                j += 1
        # add leftovers to the list

        while i < len(left_half):
            final_arr.append(left_half[i])
            i += 1
        while j < len(right_half):
            final_arr.append(right_half[j])
            j += 1

    return final_arr

arr = [1,5,8,9,4,7,0,3,5,8]

print(merge_sort(arr))

---

💡 Lessons Learned

• Splitting and recursion are the foundation of merge sort.

• Merging sorted lists is a key skill and requires a step-by-step approach.

• Understanding what happens at each recursion level helped me debug and reason through the algorithm.

• It's important to return the sorted values properly at each step.