Recursive Insertion Sort ใน Java

Recursive Insertion Sort คืออะไร?

Insertion Sort แบบ Recursive: เรียง n-1 ตัวแรก แล้ว insert ตัวที่ n เข้าไปในตำแหน่งที่ถูกต้อง

ตัวอย่างโค้ด

import java.util.Arrays; 

public class Demo { 
    static void recursiveInsertionSort(int[] arr, int n) { 
        // Base case: 0 หรือ 1 element เรียงแล้ว
        if (n <= 1) return; 
        
        // เรียง n-1 ตัวแรก
        recursiveInsertionSort(arr, n - 1); 
        
        // Insert ตัวสุดท้าย (index n-1) เข้าไปในตำแหน่งที่ถูกต้อง
        int last = arr[n - 1]; 
        int j = n - 2; 
        
        // Shift ค่าที่มากกว่า last ไปขวา
        while (j >= 0 && arr[j] > last) { 
            arr[j + 1] = arr[j]; 
            j--; 
        } 
        arr[j + 1] = last; 
    } 
    
    public static void main(String[] args) { 
        int[] arr = {11, 23, 67, 83, 42, 11, 0}; 
        
        System.out.println("ก่อน: " + Arrays.toString(arr)); 
        recursiveInsertionSort(arr, arr.length); 
        System.out.println("หลัง:  " + Arrays.toString(arr)); 
    } 
}

ผลลัพธ์

ก่อน: [11, 23, 67, 83, 42, 11, 0] 
หลัง:  [0, 11, 11, 23, 42, 67, 83]

คำอธิบาย

ฟังก์ชัน recursiveInsertionSort(arr, n) ทำงานดังนี้:

1. Base case: n ≤ 1 → return (array ขนาด 0-1 เรียงแล้ว)
2. Recursive step: เรียง n-1 ตัวแรกด้วยการเรียกตัวเอง
3. Insert: นำตัวที่ n (index n-1) ไป insert ให้อยู่ในตำแหน่งที่ถูกต้องใน subarray ที่เรียงแล้ว

Trace (arr = [3, 1, 2])

recursiveSort([3,1,2], 3)
  recursiveSort([3,1,2], 2)
    recursiveSort([3,1,2], 1) -> return
    insert index 1 (val=1): [1,3,2]
  insert index 2 (val=2): [1,2,3]

ความซับซ้อน

เปรียบเทียบ Iterative vs Recursive

ข้อควรระวัง

• Recursive version ใช้ stack space O(n) → อาจ StackOverflowError หาก n ใหญ่ (> ~10,000)
• ไม่ควรใช้กับข้อมูลขนาดใหญ่ใน production
• เหมาะสำหรับการศึกษา เข้าใจหลักการ recursion + insertion