Iterative Merge Sort ใน Java: แบบ Bottom-Up

Iterative Merge Sort (Bottom-Up)

Merge Sort แบบ Iterative เรียกว่า Bottom-Up Merge Sort เริ่มจาก merge subarray ขนาด 1 แล้วคูณ 2 ทีละขั้น จนครบ array ทั้งหมด ไม่ใช้ recursion

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

import java.util.Arrays; 

public class Demo { 
    public static void mergeSort(int[] arr) { 
        if (arr == null || arr.length <= 1) return; 
        
        int n = arr.length; 
        int[] temp = new int[n]; // temp array สำหรับ merge
        
        // width = ขนาด subarray ที่จะ merge (1, 2, 4, 8, ...)
        for (int width = 1; width < n; width *= 2) { 
            // Merge pairs of subarrays
            for (int i = 0; i < n; i += 2 * width) { 
                int left = i; 
                int mid = Math.min(i + width, n); 
                int right = Math.min(i + 2 * width, n); 
                
                merge(arr, temp, left, mid, right); 
            } 
            // Copy temp กลับ arr สำหรับรอบถัดไป
            System.arraycopy(temp, 0, arr, 0, n); 
        } 
    } 
    
    // Merge two sorted subarrays: arr[left..mid-1] และ arr[mid..right-1]
    private static void merge(int[] arr, int[] temp, int left, int mid, int right) { 
        int i = left, j = mid, k = left; 
        
        while (i < mid && j < right) { 
            temp[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++]; 
        } 
        while (i < mid) temp[k++] = arr[i++]; 
        while (j < right) temp[k++] = arr[j++]; 
    } 
    
    public static void main(String[] args) { 
        int[] arr = {56, 78, 91, 21, 34, 0, 11}; 
        
        System.out.println("ก่อน sort: " + Arrays.toString(arr)); 
        mergeSort(arr); 
        System.out.println("หลัง sort:  " + Arrays.toString(arr)); 
    } 
}

ผลลัพธ์

ก่อน sort: [56, 78, 91, 21, 34, 0, 11] 
หลัง sort:  [0, 11, 21, 34, 56, 78, 91]

คำอธิบาย

ตัวอย่างต้นฉบับเป็น Recursive Merge Sort (Top-Down) ข้างต้นเป็นเวอร์ชัน Iterative (Bottom-Up) ที่ไม่ใช้ recursion

ขั้นตอน Bottom-Up

1. เริ่ม width = 1: merge คู่ๆ ขนาด 1 → ได้ sorted runs ขนาด 2
2. width = 2: merge คู่ๆ ขนาด 2 → ได้ sorted runs ขนาด 4
3. width = 4: merge คู่ๆ ขนาด 4 → ได้ sorted runs ขนาด 8
4. ... จน width >= n

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

ข้อสังเกตจากโค้ดต้นฉบับ

• โค้ดต้นฉบับสร้าง array ใหม่ทุกครั้ง (new int[mid], new int[...]) → memory allocation มาก GC pressure สูง
• เวอร์ชันปรับปรุงใช้ temp array เดียว + System.arraycopy → เร็วกว่า ประหยัดหน่วยความจำ
• Java ใช้ Arrays.sort() (TimSort สำหรับ objects, Dual-Pivot QuickSort สำหรับ primitives) ซึ่ง optimized แล้ว