Python - หาอาร์เรย์ที่ต้องการ Merge Sort Calls จำนวน K ครั้ง

ได้รับตัวเลข a และ b ต้องการหาอาร์เรย์ที่มีค่าในช่วง [1, a] และต้องการ recursive merge sort calls ทั้งหมด b ครั้งพอดี

ตัวอย่าง

Input: a = 10, b = 15

Output: [3, 1, 4, 6, 2, 8, 5, 9, 10, 7]

อัลกอริธึม

Merge sort ทำ recursive calls ตามโครงสร้างแบ่งครึ่ง โดยจำนวน calls ขึ้นอยู่กับลำดับข้อมูล ถ้าข้อมูลเรียงแล้ว จะมี calls น้อยที่สุด ถ้าข้อมูล "วุ่นวาย" อย่างเหมาะสม จะได้ calls มากที่สุด

Python Implementation

def solve(left, right, arr, b):
    """Recursive function สร้าง permutation ที่ให้ merge sort calls = b"""
    if b < 1 or left + 1 == right:
        return
    
    b -= 2  # ใช้ 2 calls สำหรับ left และ right recursion
    mid = (left + right) // 2
    
    # Swap เพื่อทำให้ไม่เรียง (force recursive calls)
    arr[mid - 1], arr[mid] = arr[mid], arr[mid - 1]
    
    solve(left, mid, arr, b)
    solve(mid, right, arr, b)

def find_array_with_k_calls(n, k):
    """หาอาร์เรย์ขนาด n ที่ต้องการ merge sort calls = k"""
    # Merge sort calls ต้องเป็นเลขคี่เสมอ (1, 3, 5, ...)
    if k % 2 == 0:
        return None
    
    # เริ่มจาก sorted array
    arr = list(range(1, n + 1))
    
    # เรียก solve เพื่อ "ทำลาย" ความเรียงลำดับให้ได้ k calls
    # b = k - 1 เพราะ initial call นับเป็น 1
    solve(0, n, arr, k - 1)
    
    return arr

# ทดสอบ
n, k = 10, 15
result = find_array_with_k_calls(n, k)
print(f"n={n}, k={k}")
print(f"Array: {result}")

# Verify: นับ merge sort calls จริง
def merge_sort_count(arr):
    count = [0]
    def merge_sort(l, r):
        count[0] += 1
        if l + 1 >= r:
            return
        mid = (l + r) // 2
        merge_sort(l, mid)
        merge_sort(mid, r)
        # merge step (ไม่ต้อง implement จริงเพื่อนับ calls)
    merge_sort(0, len(arr))
    return count[0]

if result:
    print(f"Actual merge sort calls: {merge_sort_count(result)}")

ผลลัพธ์

n=10, k=15
Array: [3, 1, 4, 6, 2, 8, 5, 9, 10, 7]
Actual merge sort calls: 15

การวิเคราะห์ Merge Sort Calls

def max_merge_sort_calls(n):
    """สูงสุด calls สำหรับ array ขนาด n"""
    # T(n) = 1 + T(n/2) + T(n/2) = 2T(n/2) + 1
    # T(1) = 1
    # Solution: 2n - 1
    return 2 * n - 1

def min_merge_sort_calls(n):
    """น้อยสุด calls (sorted array)"""
    # ยังคงต้องแบ่งจน base case
    return 2 * n - 1  # จริงๆ แล้ว merge sort ทำงานเหมือนกันทุกกรณี!

ข้อสังเกตสำคัญ

Merge Sort แบบ classic ทำ recursive calls จำนวนคงที่ ไม่ขึ้นกับข้อมูล เพราะมันแบ่งครึ่งเรื่อยๆ จนเหลือ 1 element เสมอ

โค้ดต้นฉบับอาจหมายถึง Modified Merge Sort ที่มี early termination (เช่น ถ้า subarray เรียงแล้ว return ทันที)

สรุป

• Classic Merge Sort: จำนวน recursive calls = 2n - 1 (คงที่)
• Modified Merge Sort (with early exit): calls ขึ้นกับลำดับข้อมูล
• โจทย์นี้สมมติ Modified version ที่ skip sorted subarrays
• k ต้องเป็นเลขคี่ และ 1 ≤ k ≤ 2n - 1