ABC TO XYZ OF AI

Absolutely. Let’s now take Merge Sort, Quick Sort, and Tim Sort—three core sorting algorithms—and break them down clearly and interactively, aligned with your structured problem-solving template:

✅ Problem 1: Merge Sort

🔶 Problem Statement

Sort an unsorted array using Merge Sort.

📌 Why this Data Structure / Approach?

We use recursion + lists because:

• We divide the array into halves → naturally fits recursion.
• List slicing helps split and merge.
• Merge step uses two-pointer technique efficiently.

🧠 Pseudocode

function merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

function merge(left, right):
    i, j = 0, 0
    result = []
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result += left[i:] + right[j:]
    return result

🔄 Flow / Decision Tree

• Split until single-element arrays → base case.
• Merge sorted halves using comparison.
• Use auxiliary list to store sorted result.

✅ Code (Input → Logic → Output)

# 1. Input
def get_input():
    return [5, 2, 9, 1, 6, 3]

# 2. Process / Logic
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0

    # Compare and merge
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    # Append remaining elements
    result.extend(left[i:])
    result.extend(right[j:])
    return result

# 3. Output
def show_result(result):
    print("Sorted array:", result)

# 4. Main
def main():
    arr = get_input()
    sorted_arr = merge_sort(arr)
    show_result(sorted_arr)

main()

✅ Problem 2: Quick Sort

🔶 Problem Statement

Sort an unsorted array using Quick Sort (in-place).

📌 Why this Approach?

• Divide and Conquer + recursion
• Choose a pivot and partition into elements < and > pivot
• In-place, space-efficient

🧠 Pseudocode

function quick_sort(arr, low, high):
    if low < high:
        pivot_index = partition(arr, low, high)
        quick_sort(arr, low, pivot_index - 1)
        quick_sort(arr, pivot_index + 1, high)

function partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j from low to high-1:
        if arr[j] <= pivot:
            i += 1
            swap arr[i] with arr[j]
    swap arr[i+1] with arr[high]
    return i + 1

🔄 Flow / Decision Tree

• Choose pivot (last element).
• Rearrange array around pivot.
• Recur left and right of pivot.

✅ Code (Input → Logic → Output)

# 1. Input
def get_input():
    return [10, 7, 8, 9, 1, 5]

# 2. Logic
def quick_sort(arr, low, high):
    if low < high:
        pivot_index = partition(arr, low, high)
        quick_sort(arr, low, pivot_index - 1)
        quick_sort(arr, pivot_index + 1, high)

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1

    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]  # Swap

    arr[i+1], arr[high] = arr[high], arr[i+1]  # Final pivot swap
    return i + 1

# 3. Output
def show_result(arr):
    print("Sorted array:", arr)

# 4. Main
def main():
    arr = get_input()
    quick_sort(arr, 0, len(arr) - 1)
    show_result(arr)

main()

✅ Problem 3: Tim Sort (Python Built-in)

🔶 Problem Statement

Use Python’s built-in sort() which implements Tim Sort (hybrid of Merge + Insertion Sort).

📌 Why Tim Sort?

• Handles real-world data very efficiently.
• Detects runs (already sorted sequences).
• Combines Insertion Sort + Merge Sort.
• Python’s .sort() and sorted() use it.

✅ Code (Input → Logic → Output)

# 1. Input
def get_input():
    return [3, 7, 2, 9, 4, 1]

# 2. Logic (Using built-in Tim Sort)
def sort_array(arr):
    arr.sort()  # In-place Tim Sort
    return arr

# 3. Output
def show_result(arr):
    print("Sorted array using Tim Sort:", arr)

# 4. Main
def main():
    arr = get_input()
    sort_array(arr)
    show_result(arr)

main()

🧩 Summary Table

Pages: 1 2 3 4