MergeSort - 合併排序算法深度解析與企業應用

by Bill.Lin 32 分鐘閱讀
Algorithm

MergeSort - 合併排序算法深度解析與企業應用

1. 算法概述 (Algorithm Overview)

1.1 基本概念

MergeSort（合併排序）是一種基於分治法（Divide and Conquer）的排序算法，由約翰·馮·諾伊曼（John von Neumann）在 1945 年發明。作為一種穩定的排序算法，MergeSort 在處理大量數據時表現出色，特別適合企業級應用中的數據處理場景。

1.2 核心思想

正如柯P所說：小問題解決了，就沒有大問題了。MergeSort 的核心思想體現在：

  1. 分割（Divide）：將 n 個元素的數組遞歸地分成兩個各含 n/2 個元素的子數組
  2. 征服（Conquer）：遞歸地排序兩個子數組
  3. 合併（Merge）：將兩個已排序的子數組合併成一個排序好的數組

1.3 算法特性

1
2
3
4

// 時間複雜度：O(n log n) - 最佳、平均、最壞情況都相同
// 空間複雜度：O(n) - 需要額外的輔助數組
// 穩定性：穩定排序（相等元素的相對位置不變）
// 適用性：適合大量數據、外部排序、並行處理

2. 複雜度分析 (Complexity Analysis)

2.1 時間複雜度詳細分析

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

/**
 * MergeSort 時間複雜度分析
 * 
 * T(n) = 2T(n/2) + O(n)
 * 
 * 根據主定理 (Master Theorem)：
 * a = 2, b = 2, f(n) = n
 * log_b(a) = log_2(2) = 1
 * f(n) = n = Θ(n^1)
 * 
 * 因此：T(n) = Θ(n log n)
 */
public class ComplexityAnalysis {
    
    // 遞歸深度：log₂(n)
    // 每層合併：O(n)
    // 總時間複雜度：O(n log n)
    
    public static void analyzeComplexity(int n) {
        int levels = (int) Math.ceil(Math.log(n) / Math.log(2));
        System.out.printf("Array size: %d, Recursion levels: %d%n", n, levels);
        System.out.printf("Time complexity: O(%d log %d) = O(%d)%n", 
                         n, n, (int)(n * Math.log(n) / Math.log(2)));
    }
}

2.2 空間複雜度分析

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

/**
 * 空間複雜度組成：
 * 1. 遞歸調用棧：O(log n)
 * 2. 輔助數組：O(n)
 * 3. 總空間複雜度：O(n)
 */
public class SpaceComplexityDemo {
    
    private static int maxDepth = 0;
    private static int currentDepth = 0;
    
    public static void trackSpaceUsage(int[] array, int depth) {
        currentDepth = depth;
        maxDepth = Math.max(maxDepth, currentDepth);
        
        // 輔助數組空間
        int[] auxiliary = new int[array.length];
        
        System.out.printf("Depth: %d, Auxiliary array size: %d%n", 
                         depth, auxiliary.length);
    }
}

3. 基礎實現 (Basic Implementation)

3.1 經典遞歸實現

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

/**
 * 經典 MergeSort 遞歸實現
 * 時間複雜度：O(n log n)
 * 空間複雜度：O(n)
 */
public class ClassicMergeSort {
    
    /**
     * 主排序方法
     */
    public static void mergeSort(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }
        
        int[] auxiliary = new int[array.length];
        mergeSortHelper(array, auxiliary, 0, array.length - 1);
    }
    
    /**
     * 遞歸排序輔助方法
     */
    private static void mergeSortHelper(int[] array, int[] auxiliary, 
                                       int start, int end) {
        if (start >= end) {
            return;
        }
        
        // 避免整數溢出的中點計算
        int mid = start + (end - start) / 2;
        
        // 遞歸排序左半部分
        mergeSortHelper(array, auxiliary, start, mid);
        
        // 遞歸排序右半部分
        mergeSortHelper(array, auxiliary, mid + 1, end);
        
        // 合併已排序的兩部分
        merge(array, auxiliary, start, mid, end);
    }
    
    /**
     * 合併兩個已排序的子數組
     */
    private static void merge(int[] array, int[] auxiliary, 
                             int start, int mid, int end) {
        // 複製到輔助數組
        System.arraycopy(array, start, auxiliary, start, end - start + 1);
        
        int leftPtr = start;      // 左子數組指針
        int rightPtr = mid + 1;   // 右子數組指針
        int index = start;        // 合併結果指針
        
        // 合併過程
        while (leftPtr <= mid && rightPtr <= end) {
            if (auxiliary[leftPtr] <= auxiliary[rightPtr]) {
                array[index++] = auxiliary[leftPtr++];
            } else {
                array[index++] = auxiliary[rightPtr++];
            }
        }
        
        // 處理剩餘元素
        while (leftPtr <= mid) {
            array[index++] = auxiliary[leftPtr++];
        }
        
        while (rightPtr <= end) {
            array[index++] = auxiliary[rightPtr++];
        }
    }
}

3.2 優化版實現

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

/**
 * 優化版 MergeSort 實現
 * 包含多種優化技術
 */
public class OptimizedMergeSort {
    
    private static final int INSERTION_SORT_THRESHOLD = 7;
    
    /**
     * 優化版合併排序
     */
    public static void optimizedMergeSort(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }
        
        int[] auxiliary = new int[array.length];
        optimizedMergeSortHelper(array, auxiliary, 0, array.length - 1);
    }
    
    private static void optimizedMergeSortHelper(int[] array, int[] auxiliary, 
                                               int start, int end) {
        // 優化1：對小數組使用插入排序
        if (end - start + 1 <= INSERTION_SORT_THRESHOLD) {
            insertionSort(array, start, end);
            return;
        }
        
        int mid = start + (end - start) / 2;
        
        optimizedMergeSortHelper(array, auxiliary, start, mid);
        optimizedMergeSortHelper(array, auxiliary, mid + 1, end);
        
        // 優化2：檢查是否已經排序好
        if (array[mid] <= array[mid + 1]) {
            return; // 已經排序好，無需合併
        }
        
        merge(array, auxiliary, start, mid, end);
    }
    
    /**
     * 插入排序 - 用於小數組優化
     */
    private static void insertionSort(int[] array, int start, int end) {
        for (int i = start + 1; i <= end; i++) {
            int key = array[i];
            int j = i - 1;
            
            while (j >= start && array[j] > key) {
                array[j + 1] = array[j];
                j--;
            }
            
            array[j + 1] = key;
        }
    }
    
    private static void merge(int[] array, int[] auxiliary, 
                             int start, int mid, int end) {
        // 優化3：只複製左半部分到輔助數組
        System.arraycopy(array, start, auxiliary, start, mid - start + 1);
        
        int leftPtr = start;
        int rightPtr = mid + 1;
        int index = start;
        
        while (leftPtr <= mid && rightPtr <= end) {
            if (auxiliary[leftPtr] <= array[rightPtr]) {
                array[index++] = auxiliary[leftPtr++];
            } else {
                array[index++] = array[rightPtr++];
            }
        }
        
        while (leftPtr <= mid) {
            array[index++] = auxiliary[leftPtr++];
        }
    }
}

4. 現代 Java 實現 (Modern Java Implementation)

4.1 使用泛型和函數式接口

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

import java.util.Comparator;
import java.util.function.Function;

/**
 * 現代 Java 泛型 MergeSort 實現
 * 支持自定義比較器和函數式編程
 */
public class ModernMergeSort {
    
    /**
     * 泛型合併排序
     */
    public static <T> void mergeSort(T[] array, Comparator<T> comparator) {
        if (array == null || array.length <= 1) {
            return;
        }
        
        @SuppressWarnings("unchecked")
        T[] auxiliary = (T[]) new Object[array.length];
        mergeSortHelper(array, auxiliary, 0, array.length - 1, comparator);
    }
    
    private static <T> void mergeSortHelper(T[] array, T[] auxiliary, 
                                          int start, int end, 
                                          Comparator<T> comparator) {
        if (start >= end) {
            return;
        }
        
        int mid = start + (end - start) / 2;
        
        mergeSortHelper(array, auxiliary, start, mid, comparator);
        mergeSortHelper(array, auxiliary, mid + 1, end, comparator);
        merge(array, auxiliary, start, mid, end, comparator);
    }
    
    private static <T> void merge(T[] array, T[] auxiliary, 
                                 int start, int mid, int end, 
                                 Comparator<T> comparator) {
        System.arraycopy(array, start, auxiliary, start, end - start + 1);
        
        int leftPtr = start;
        int rightPtr = mid + 1;
        int index = start;
        
        while (leftPtr <= mid && rightPtr <= end) {
            if (comparator.compare(auxiliary[leftPtr], auxiliary[rightPtr]) <= 0) {
                array[index++] = auxiliary[leftPtr++];
            } else {
                array[index++] = auxiliary[rightPtr++];
            }
        }
        
        while (leftPtr <= mid) {
            array[index++] = auxiliary[leftPtr++];
        }
        
        while (rightPtr <= end) {
            array[index++] = auxiliary[rightPtr++];
        }
    }
    
    /**
     * 使用 Stream API 的函數式排序
     */
    public static <T, R extends Comparable<R>> T[] sortByKey(
            T[] array, Function<T, R> keyExtractor) {
        
        return java.util.Arrays.stream(array)
                .sorted(Comparator.comparing(keyExtractor))
                .toArray(size -> java.util.Arrays.copyOf(array, size));
    }
}

4.2 並行 MergeSort 實現

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;

/**
 * 並行 MergeSort 實現
 * 利用 ForkJoinPool 進行並行處理
 */
public class ParallelMergeSort {
    
    private static final int PARALLEL_THRESHOLD = 8192;
    
    /**
     * 並行合併排序入口
     */
    public static void parallelMergeSort(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }
        
        ForkJoinPool pool = ForkJoinPool.commonPool();
        pool.invoke(new MergeSortTask(array, 0, array.length - 1));
    }
    
    /**
     * ForkJoin 任務類
     */
    private static class MergeSortTask extends RecursiveAction {
        private final int[] array;
        private final int start;
        private final int end;
        
        public MergeSortTask(int[] array, int start, int end) {
            this.array = array;
            this.start = start;
            this.end = end;
        }
        
        @Override
        protected void compute() {
            if (end - start + 1 <= PARALLEL_THRESHOLD) {
                // 小數組使用順序排序
                ClassicMergeSort.mergeSort(
                    java.util.Arrays.copyOfRange(array, start, end + 1)
                );
                return;
            }
            
            int mid = start + (end - start) / 2;
            
            // 創建並行任務
            MergeSortTask leftTask = new MergeSortTask(array, start, mid);
            MergeSortTask rightTask = new MergeSortTask(array, mid + 1, end);
            
            // 並行執行
            invokeAll(leftTask, rightTask);
            
            // 合併結果
            merge(array, start, mid, end);
        }
        
        private void merge(int[] array, int start, int mid, int end) {
            int[] auxiliary = new int[end - start + 1];
            System.arraycopy(array, start, auxiliary, 0, auxiliary.length);
            
            int leftPtr = 0;
            int rightPtr = mid - start + 1;
            int index = start;
            
            while (leftPtr <= mid - start && rightPtr < auxiliary.length) {
                if (auxiliary[leftPtr] <= auxiliary[rightPtr]) {
                    array[index++] = auxiliary[leftPtr++];
                } else {
                    array[index++] = auxiliary[rightPtr++];
                }
            }
            
            while (leftPtr <= mid - start) {
                array[index++] = auxiliary[leftPtr++];
            }
            
            while (rightPtr < auxiliary.length) {
                array[index++] = auxiliary[rightPtr++];
            }
        }
    }
}

5. 迭代實現 (Iterative Implementation)

5.1 自底向上合併排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

/**
 * 迭代版 MergeSort 實現
 * 自底向上的合併方式，避免遞歸調用
 */
public class IterativeMergeSort {
    
    /**
     * 迭代版合併排序
     */
    public static void iterativeMergeSort(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }
        
        int n = array.length;
        int[] auxiliary = new int[n];
        
        // 從長度為 1 的子數組開始合併
        for (int size = 1; size < n; size *= 2) {
            for (int start = 0; start < n - size; start += 2 * size) {
                int mid = start + size - 1;
                int end = Math.min(start + 2 * size - 1, n - 1);
                
                merge(array, auxiliary, start, mid, end);
            }
        }
    }
    
    private static void merge(int[] array, int[] auxiliary, 
                             int start, int mid, int end) {
        System.arraycopy(array, start, auxiliary, start, end - start + 1);
        
        int leftPtr = start;
        int rightPtr = mid + 1;
        int index = start;
        
        while (leftPtr <= mid && rightPtr <= end) {
            if (auxiliary[leftPtr] <= auxiliary[rightPtr]) {
                array[index++] = auxiliary[leftPtr++];
            } else {
                array[index++] = auxiliary[rightPtr++];
            }
        }
        
        while (leftPtr <= mid) {
            array[index++] = auxiliary[leftPtr++];
        }
        
        while (rightPtr <= end) {
            array[index++] = auxiliary[rightPtr++];
        }
    }
    
    /**
     * 追蹤迭代過程的調試版本
     */
    public static void iterativeMergeSortWithTrace(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }
        
        int n = array.length;
        int[] auxiliary = new int[n];
        
        System.out.println("迭代合併排序過程追蹤：");
        System.out.println("初始數組：" + java.util.Arrays.toString(array));
        
        for (int size = 1; size < n; size *= 2) {
            System.out.printf("合併大小：%d%n", size);
            
            for (int start = 0; start < n - size; start += 2 * size) {
                int mid = start + size - 1;
                int end = Math.min(start + 2 * size - 1, n - 1);
                
                System.out.printf("  合併範圍：[%d, %d, %d]%n", start, mid, end);
                merge(array, auxiliary, start, mid, end);
                System.out.printf("  結果：%s%n", 
                                java.util.Arrays.toString(array));
            }
        }
    }
}

6. 企業級應用場景 (Enterprise Use Cases)

6.1 大數據排序服務

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

import org.springframework.stereotype.Service;
import org.springframework.beans.factory.annotation.Autowired;
import java.util.concurrent.CompletableFuture;
import java.util.concurrent.ExecutorService;

/**
 * 企業級大數據排序服務
 * 支持多種排序策略和性能監控
 */
@Service
public class EnterpriseDataSortingService {
    
    @Autowired
    private PerformanceMonitoringService monitoringService;
    
    @Autowired
    private ExecutorService sortingExecutorService;
    
    /**
     * 異步大數據排序
     */
    public CompletableFuture<int[]> sortLargeDatasetAsync(int[] data) {
        return CompletableFuture.supplyAsync(() -> {
            long startTime = System.nanoTime();
            
            try {
                // 根據數據大小選擇排序策略
                if (data.length > 100_000) {
                    ParallelMergeSort.parallelMergeSort(data);
                } else {
                    OptimizedMergeSort.optimizedMergeSort(data);
                }
                
                return data;
            } finally {
                long endTime = System.nanoTime();
                monitoringService.recordSortingMetrics(
                    data.length, (endTime - startTime) / 1_000_000
                );
            }
        }, sortingExecutorService);
    }
    
    /**
     * 批量數據排序處理
     */
    public void processBatchData(java.util.List<int[]> datasets) {
        datasets.parallelStream()
                .forEach(dataset -> {
                    if (dataset.length > 50_000) {
                        ParallelMergeSort.parallelMergeSort(dataset);
                    } else {
                        ClassicMergeSort.mergeSort(dataset);
                    }
                });
    }
}

6.2 數據庫記錄排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

import javax.persistence.Entity;
import javax.persistence.Table;
import javax.persistence.Id;
import javax.persistence.GeneratedValue;
import java.time.LocalDateTime;
import java.util.Comparator;

/**
 * 數據庫記錄實體
 */
@Entity
@Table(name = "transaction_records")
public class TransactionRecord {
    @Id
    @GeneratedValue
    private Long id;
    
    private String customerId;
    private Double amount;
    private LocalDateTime timestamp;
    private String status;
    
    // 構造函數、getter、setter 省略
    
    /**
     * 多字段排序比較器
     */
    public static final Comparator<TransactionRecord> MULTI_FIELD_COMPARATOR = 
        Comparator.comparing(TransactionRecord::getTimestamp)
                  .thenComparing(TransactionRecord::getAmount)
                  .thenComparing(TransactionRecord::getCustomerId);
}

/**
 * 企業級記錄排序服務
 */
@Service
public class RecordSortingService {
    
    /**
     * 交易記錄排序處理
     */
    public TransactionRecord[] sortTransactionRecords(
            TransactionRecord[] records, 
            Comparator<TransactionRecord> comparator) {
        
        ModernMergeSort.mergeSort(records, comparator);
        return records;
    }
    
    /**
     * 基於時間範圍的記錄排序
     */
    public java.util.List<TransactionRecord> sortRecordsByTimeRange(
            java.util.List<TransactionRecord> records,
            LocalDateTime startTime,
            LocalDateTime endTime) {
        
        return records.stream()
                     .filter(record -> isInTimeRange(record, startTime, endTime))
                     .sorted(TransactionRecord.MULTI_FIELD_COMPARATOR)
                     .collect(java.util.stream.Collectors.toList());
    }
    
    private boolean isInTimeRange(TransactionRecord record, 
                                 LocalDateTime start, LocalDateTime end) {
        LocalDateTime timestamp = record.getTimestamp();
        return timestamp.isAfter(start) && timestamp.isBefore(end);
    }
}

7. Spring Boot 整合 (Spring Boot Integration)

7.1 排序配置和 Bean 定義

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

import org.springframework.boot.SpringApplication;
import org.springframework.boot.autoconfigure.SpringBootApplication;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;
import org.springframework.scheduling.annotation.EnableAsync;
import org.springframework.scheduling.concurrent.ThreadPoolTaskExecutor;

import java.util.concurrent.ExecutorService;

/**
 * Spring Boot 排序服務配置
 */
@SpringBootApplication
@EnableAsync
public class SortingServiceApplication {
    
    public static void main(String[] args) {
        SpringApplication.run(SortingServiceApplication.class, args);
    }
}

@Configuration
public class SortingConfiguration {
    
    /**
     * 排序專用線程池
     */
    @Bean
    public ExecutorService sortingExecutorService() {
        ThreadPoolTaskExecutor executor = new ThreadPoolTaskExecutor();
        executor.setCorePoolSize(4);
        executor.setMaxPoolSize(8);
        executor.setQueueCapacity(100);
        executor.setThreadNamePrefix("sorting-");
        executor.initialize();
        return executor.getThreadPoolExecutor();
    }
    
    /**
     * 排序策略工廠
     */
    @Bean
    public SortingStrategyFactory sortingStrategyFactory() {
        return new SortingStrategyFactory();
    }
}

7.2 RESTful 排序 API

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

import org.springframework.web.bind.annotation.*;
import org.springframework.http.ResponseEntity;
import org.springframework.beans.factory.annotation.Autowired;
import java.util.concurrent.CompletableFuture;

/**
 * 排序服務 REST API
 */
@RestController
@RequestMapping("/api/sorting")
public class SortingController {
    
    @Autowired
    private EnterpriseDataSortingService sortingService;
    
    /**
     * 同步排序 API
     */
    @PostMapping("/sort")
    public ResponseEntity<int[]> sortData(@RequestBody int[] data) {
        if (data.length > 10_000) {
            ParallelMergeSort.parallelMergeSort(data);
        } else {
            ClassicMergeSort.mergeSort(data);
        }
        
        return ResponseEntity.ok(data);
    }
    
    /**
     * 異步排序 API
     */
    @PostMapping("/sort/async")
    public CompletableFuture<ResponseEntity<int[]>> sortDataAsync(
            @RequestBody int[] data) {
        
        return sortingService.sortLargeDatasetAsync(data)
                           .thenApply(ResponseEntity::ok);
    }
    
    /**
     * 自定義排序策略 API
     */
    @PostMapping("/sort/custom")
    public ResponseEntity<TransactionRecord[]> sortWithStrategy(
            @RequestBody TransactionRecord[] records,
            @RequestParam String strategy) {
        
        java.util.Comparator<TransactionRecord> comparator = 
            getComparatorByStrategy(strategy);
        
        ModernMergeSort.mergeSort(records, comparator);
        return ResponseEntity.ok(records);
    }
    
    private java.util.Comparator<TransactionRecord> getComparatorByStrategy(String strategy) {
        switch (strategy.toLowerCase()) {
            case "amount":
                return java.util.Comparator.comparing(TransactionRecord::getAmount);
            case "time":
                return java.util.Comparator.comparing(TransactionRecord::getTimestamp);
            case "customer":
                return java.util.Comparator.comparing(TransactionRecord::getCustomerId);
            default:
                return TransactionRecord.MULTI_FIELD_COMPARATOR;
        }
    }
}

8. 性能監控和指標 (Performance Monitoring)

8.1 排序性能監控服務

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

import org.springframework.stereotype.Service;
import io.micrometer.core.instrument.MeterRegistry;
import io.micrometer.core.instrument.Timer;
import java.util.concurrent.atomic.AtomicLong;

/**
 * 排序性能監控服務
 */
@Service
public class PerformanceMonitoringService {
    
    private final MeterRegistry meterRegistry;
    private final Timer sortingTimer;
    private final AtomicLong totalSortedItems = new AtomicLong(0);
    
    public PerformanceMonitoringService(MeterRegistry meterRegistry) {
        this.meterRegistry = meterRegistry;
        this.sortingTimer = Timer.builder("sorting.duration")
                                .description("Time taken to sort data")
                                .register(meterRegistry);
    }
    
    /**
     * 記錄排序指標
     */
    public void recordSortingMetrics(int dataSize, long durationMs) {
        // 記錄排序時間
        sortingTimer.record(durationMs, java.util.concurrent.TimeUnit.MILLISECONDS);
        
        // 記錄數據大小
        meterRegistry.counter("sorting.data.size").increment(dataSize);
        
        // 更新總排序項目數
        totalSortedItems.addAndGet(dataSize);
        
        // 記錄性能比率（項目/毫秒）
        if (durationMs > 0) {
            double itemsPerMs = (double) dataSize / durationMs;
            meterRegistry.gauge("sorting.performance.items_per_ms", itemsPerMs);
        }
    }
    
    /**
     * 獲取性能統計
     */
    public SortingPerformanceStats getPerformanceStats() {
        return new SortingPerformanceStats(
            sortingTimer.count(),
            sortingTimer.totalTime(java.util.concurrent.TimeUnit.MILLISECONDS),
            totalSortedItems.get(),
            sortingTimer.mean(java.util.concurrent.TimeUnit.MILLISECONDS)
        );
    }
}

/**
 * 性能統計數據類
 */
public class SortingPerformanceStats {
    private final long totalSortOperations;
    private final double totalTimeMs;
    private final long totalItemsSorted;
    private final double averageTimeMs;
    
    // 構造函數和 getter 方法
    public SortingPerformanceStats(long totalSortOperations, double totalTimeMs, 
                                 long totalItemsSorted, double averageTimeMs) {
        this.totalSortOperations = totalSortOperations;
        this.totalTimeMs = totalTimeMs;
        this.totalItemsSorted = totalItemsSorted;
        this.averageTimeMs = averageTimeMs;
    }
    
    // getter 方法省略
}

8.2 性能基準測試

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

import org.springframework.boot.CommandLineRunner;
import org.springframework.stereotype.Component;
import java.util.Random;

/**
 * 排序算法性能基準測試
 */
@Component
public class SortingBenchmark implements CommandLineRunner {
    
    @Override
    public void run(String... args) throws Exception {
        runBenchmarkSuite();
    }
    
    /**
     * 執行完整的基準測試套件
     */
    public void runBenchmarkSuite() {
        int[] sizes = {1000, 10000, 100000, 1000000};
        
        System.out.println("=== MergeSort 性能基準測試 ===");
        System.out.printf("%-15s %-15s %-15s %-15s%n", 
                         "數據大小", "經典版本(ms)", "優化版本(ms)", "並行版本(ms)");
        
        for (int size : sizes) {
            benchmarkSize(size);
        }
    }
    
    private void benchmarkSize(int size) {
        int[] testData = generateRandomData(size);
        
        // 測試經典版本
        int[] data1 = testData.clone();
        long start1 = System.nanoTime();
        ClassicMergeSort.mergeSort(data1);
        long time1 = (System.nanoTime() - start1) / 1_000_000;
        
        // 測試優化版本
        int[] data2 = testData.clone();
        long start2 = System.nanoTime();
        OptimizedMergeSort.optimizedMergeSort(data2);
        long time2 = (System.nanoTime() - start2) / 1_000_000;
        
        // 測試並行版本
        int[] data3 = testData.clone();
        long start3 = System.nanoTime();
        ParallelMergeSort.parallelMergeSort(data3);
        long time3 = (System.nanoTime() - start3) / 1_000_000;
        
        System.out.printf("%-15d %-15d %-15d %-15d%n", 
                         size, time1, time2, time3);
    }
    
    private int[] generateRandomData(int size) {
        Random random = new Random(42); // 固定種子保證可重現性
        int[] data = new int[size];
        for (int i = 0; i < size; i++) {
            data[i] = random.nextInt(size * 10);
        }
        return data;
    }
}

9. 外部排序和大文件處理 (External Sorting)

9.1 外部合併排序實現

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157

import java.io.*;
import java.nio.file.*;
import java.util.List;
import java.util.ArrayList;
import java.util.PriorityQueue;

/**
 * 外部合併排序實現
 * 用於處理無法完全加載到內存的大文件
 */
public class ExternalMergeSort {
    
    private static final int CHUNK_SIZE = 1000000; // 每個塊的大小
    
    /**
     * 外部排序主方法
     */
    public static void externalSort(String inputFile, String outputFile) 
            throws IOException {
        
        // 第一階段：分割和排序小塊
        List<String> tempFiles = splitAndSortChunks(inputFile);
        
        // 第二階段：合併所有小塊
        mergeChunks(tempFiles, outputFile);
        
        // 清理臨時文件
        for (String tempFile : tempFiles) {
            Files.deleteIfExists(Paths.get(tempFile));
        }
    }
    
    /**
     * 分割大文件並排序每個小塊
     */
    private static List<String> splitAndSortChunks(String inputFile) 
            throws IOException {
        
        List<String> tempFiles = new ArrayList<>();
        
        try (BufferedReader reader = Files.newBufferedReader(Paths.get(inputFile))) {
            List<Integer> chunk = new ArrayList<>();
            String line;
            int fileIndex = 0;
            
            while ((line = reader.readLine()) != null) {
                chunk.add(Integer.parseInt(line.trim()));
                
                if (chunk.size() >= CHUNK_SIZE) {
                    String tempFile = sortAndSaveChunk(chunk, fileIndex++);
                    tempFiles.add(tempFile);
                    chunk.clear();
                }
            }
            
            // 處理最後一個塊
            if (!chunk.isEmpty()) {
                String tempFile = sortAndSaveChunk(chunk, fileIndex);
                tempFiles.add(tempFile);
            }
        }
        
        return tempFiles;
    }
    
    /**
     * 排序並保存單個塊
     */
    private static String sortAndSaveChunk(List<Integer> chunk, int index) 
            throws IOException {
        
        // 使用合併排序對塊進行排序
        int[] array = chunk.stream().mapToInt(Integer::intValue).toArray();
        ClassicMergeSort.mergeSort(array);
        
        // 保存到臨時文件
        String tempFileName = "temp_chunk_" + index + ".txt";
        try (BufferedWriter writer = Files.newBufferedWriter(Paths.get(tempFileName))) {
            for (int value : array) {
                writer.write(value + "\n");
            }
        }
        
        return tempFileName;
    }
    
    /**
     * 使用多路合併算法合併所有排序好的塊
     */
    private static void mergeChunks(List<String> tempFiles, String outputFile) 
            throws IOException {
        
        // 使用優先隊列進行多路合併
        PriorityQueue<ChunkReader> pq = new PriorityQueue<>(
            (a, b) -> Integer.compare(a.peek(), b.peek())
        );
        
        // 初始化所有塊讀取器
        for (String tempFile : tempFiles) {
            ChunkReader reader = new ChunkReader(tempFile);
            if (reader.hasNext()) {
                pq.offer(reader);
            }
        }
        
        // 合併寫入輸出文件
        try (BufferedWriter writer = Files.newBufferedWriter(Paths.get(outputFile))) {
            while (!pq.isEmpty()) {
                ChunkReader minReader = pq.poll();
                writer.write(minReader.next() + "\n");
                
                if (minReader.hasNext()) {
                    pq.offer(minReader);
                } else {
                    minReader.close();
                }
            }
        }
    }
    
    /**
     * 塊文件讀取器
     */
    private static class ChunkReader implements AutoCloseable {
        private final BufferedReader reader;
        private Integer nextValue;
        
        public ChunkReader(String fileName) throws IOException {
            this.reader = Files.newBufferedReader(Paths.get(fileName));
            advance();
        }
        
        public boolean hasNext() {
            return nextValue != null;
        }
        
        public int peek() {
            return nextValue;
        }
        
        public int next() throws IOException {
            int current = nextValue;
            advance();
            return current;
        }
        
        private void advance() throws IOException {
            String line = reader.readLine();
            nextValue = (line != null) ? Integer.parseInt(line.trim()) : null;
        }
        
        @Override
        public void close() throws IOException {
            reader.close();
        }
    }
}

10. 與其他排序算法比較 (Algorithm Comparison)

10.1 排序算法比較分析

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

/**
 * 排序算法比較和分析
 */
public class SortingAlgorithmComparison {
    
    /**
     * 排序算法特性比較
     */
    public static void compareAlgorithmCharacteristics() {
        System.out.println("=== 排序算法特性比較 ===");
        System.out.printf("%-15s %-15s %-15s %-10s %-10s%n",
                         "算法", "時間複雜度", "空間複雜度", "穩定性", "適用場景");
        System.out.println("-".repeat(70));
        
        printAlgorithmInfo("MergeSort", "O(n log n)", "O(n)", "穩定", "大數據集");
        printAlgorithmInfo("QuickSort", "O(n log n)", "O(log n)", "不穩定", "一般用途");
        printAlgorithmInfo("HeapSort", "O(n log n)", "O(1)", "不穩定", "內存受限");
        printAlgorithmInfo("BubbleSort", "O(n²)", "O(1)", "穩定", "教學用途");
        printAlgorithmInfo("InsertionSort", "O(n²)", "O(1)", "穩定", "小數組");
        printAlgorithmInfo("SelectionSort", "O(n²)", "O(1)", "不穩定", "簡單實現");
    }
    
    private static void printAlgorithmInfo(String name, String timeComplexity, 
                                         String spaceComplexity, String stability, 
                                         String useCase) {
        System.out.printf("%-15s %-15s %-15s %-10s %-10s%n",
                         name, timeComplexity, spaceComplexity, stability, useCase);
    }
    
    /**
     * 實際性能測試比較
     */
    public static void performanceComparison(int size) {
        int[] testData = generateRandomData(size);
        
        System.out.printf("=== 數組大小 %d 的性能比較 ===%n", size);
        
        // MergeSort 測試
        int[] mergeSortData = testData.clone();
        long mergeTime = timeSort(() -> ClassicMergeSort.mergeSort(mergeSortData));
        
        // Java 內置排序測試（TimSort，基於 MergeSort 和 InsertionSort）
        int[] javaData = testData.clone();
        long javaTime = timeSort(() -> java.util.Arrays.sort(javaData));
        
        // 並行 MergeSort 測試
        int[] parallelData = testData.clone();
        long parallelTime = timeSort(() -> ParallelMergeSort.parallelMergeSort(parallelData));
        
        System.out.printf("MergeSort（經典）: %d ms%n", mergeTime);
        System.out.printf("Java Arrays.sort: %d ms%n", javaTime);
        System.out.printf("並行 MergeSort: %d ms%n", parallelTime);
        
        // 驗證排序正確性
        boolean mergeSorted = isSorted(mergeSortData);
        boolean javaSorted = isSorted(javaData);
        boolean parallelSorted = isSorted(parallelData);
        
        System.out.printf("排序正確性 - MergeSort: %s, Java: %s, 並行: %s%n",
                         mergeSorted, javaSorted, parallelSorted);
    }
    
    private static long timeSort(Runnable sortOperation) {
        long start = System.nanoTime();
        sortOperation.run();
        return (System.nanoTime() - start) / 1_000_000; // 轉換為毫秒
    }
    
    private static boolean isSorted(int[] array) {
        for (int i = 1; i < array.length; i++) {
            if (array[i] < array[i - 1]) {
                return false;
            }
        }
        return true;
    }
    
    private static int[] generateRandomData(int size) {
        java.util.Random random = new java.util.Random(42);
        int[] data = new int[size];
        for (int i = 0; i < size; i++) {
            data[i] = random.nextInt(size * 10);
        }
        return data;
    }
}

11. 測試策略 (Testing Strategy)

11.1 單元測試

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113

import org.junit.jupiter.api.Test;
import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.ValueSource;
import static org.junit.jupiter.api.Assertions.*;
import java.util.Arrays;
import java.util.Random;

/**
 * MergeSort 單元測試
 */
class MergeSortTest {
    
    @Test
    @DisplayName("測試空數組")
    void testEmptyArray() {
        int[] array = {};
        ClassicMergeSort.mergeSort(array);
        assertEquals(0, array.length);
    }
    
    @Test
    @DisplayName("測試單元素數組")
    void testSingleElement() {
        int[] array = {42};
        ClassicMergeSort.mergeSort(array);
        assertArrayEquals(new int[]{42}, array);
    }
    
    @Test
    @DisplayName("測試已排序數組")
    void testAlreadySorted() {
        int[] array = {1, 2, 3, 4, 5};
        int[] expected = array.clone();
        ClassicMergeSort.mergeSort(array);
        assertArrayEquals(expected, array);
    }
    
    @Test
    @DisplayName("測試逆序數組")
    void testReverseSorted() {
        int[] array = {5, 4, 3, 2, 1};
        int[] expected = {1, 2, 3, 4, 5};
        ClassicMergeSort.mergeSort(array);
        assertArrayEquals(expected, array);
    }
    
    @Test
    @DisplayName("測試重複元素")
    void testDuplicateElements() {
        int[] array = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
        int[] expected = {1, 1, 2, 3, 3, 4, 5, 5, 6, 9};
        ClassicMergeSort.mergeSort(array);
        assertArrayEquals(expected, array);
    }
    
    @ParameterizedTest
    @ValueSource(ints = {10, 100, 1000, 10000})
    @DisplayName("測試不同大小的隨機數組")
    void testRandomArrays(int size) {
        int[] array = generateRandomArray(size);
        int[] expected = array.clone();
        Arrays.sort(expected); // 使用 Java 內置排序作為標準
        
        ClassicMergeSort.mergeSort(array);
        assertArrayEquals(expected, array);
    }
    
    @Test
    @DisplayName("測試穩定性")
    void testStability() {
        // 使用自定義對象測試穩定性
        class StableTestObject {
            final int value;
            final int order;
            
            StableTestObject(int value, int order) {
                this.value = value;
                this.order = order;
            }
        }
        
        StableTestObject[] array = {
            new StableTestObject(3, 1),
            new StableTestObject(1, 1),
            new StableTestObject(3, 2),
            new StableTestObject(2, 1),
            new StableTestObject(3, 3)
        };
        
        ModernMergeSort.mergeSort(array, 
            java.util.Comparator.comparing(obj -> obj.value));
        
        // 驗證相同值的元素保持原始順序
        assertEquals(1, array[0].value);
        assertEquals(2, array[1].value);
        assertEquals(3, array[2].value);
        assertEquals(1, array[2].order); // 第一個 3
        assertEquals(3, array[3].value);
        assertEquals(2, array[3].order); // 第二個 3
        assertEquals(3, array[4].value);
        assertEquals(3, array[4].order); // 第三個 3
    }
    
    private int[] generateRandomArray(int size) {
        Random random = new Random(System.currentTimeMillis());
        int[] array = new int[size];
        for (int i = 0; i < size; i++) {
            array[i] = random.nextInt(size * 2);
        }
        return array;
    }
}

11.2 性能測試

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

import org.junit.jupiter.api.Test;
import org.junit.jupiter.api.RepeatedTest;
import org.junit.jupiter.api.Timeout;
import java.util.concurrent.TimeUnit;

/**
 * MergeSort 性能測試
 */
class MergeSortPerformanceTest {
    
    @Test
    @Timeout(value = 5, unit = TimeUnit.SECONDS)
    @DisplayName("大數組排序性能測試")
    void testLargeArrayPerformance() {
        int[] largeArray = generateRandomArray(1_000_000);
        ClassicMergeSort.mergeSort(largeArray);
        assertTrue(isSorted(largeArray));
    }
    
    @RepeatedTest(10)
    @DisplayName("並行版本性能一致性測試")
    void testParallelConsistency() {
        int[] array = generateRandomArray(100_000);
        int[] expected = array.clone();
        Arrays.sort(expected);
        
        ParallelMergeSort.parallelMergeSort(array);
        assertArrayEquals(expected, array);
    }
    
    @Test
    @DisplayName("內存使用測試")
    void testMemoryUsage() {
        Runtime runtime = Runtime.getRuntime();
        long memoryBefore = runtime.totalMemory() - runtime.freeMemory();
        
        int[] array = generateRandomArray(500_000);
        ClassicMergeSort.mergeSort(array);
        
        System.gc(); // 建議垃圾回收
        long memoryAfter = runtime.totalMemory() - runtime.freeMemory();
        
        // 驗證內存使用在合理範圍內
        long memoryUsed = memoryAfter - memoryBefore;
        assertTrue(memoryUsed < array.length * 8); // 合理的內存使用預期
    }
    
    private int[] generateRandomArray(int size) {
        java.util.Random random = new java.util.Random(42);
        int[] array = new int[size];
        for (int i = 0; i < size; i++) {
            array[i] = random.nextInt(size * 2);
        }
        return array;
    }
    
    private boolean isSorted(int[] array) {
        for (int i = 1; i < array.length; i++) {
            if (array[i] < array[i - 1]) {
                return false;
            }
        }
        return true;
    }
}

12. 最佳實踐和反模式 (Best Practices and Anti-patterns)

12.1 最佳實踐

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

/**
 * MergeSort 最佳實踐指南
 */
public class MergeSortBestPractices {
    
    /**
     * 1. 參數驗證
     */
    public static void mergeSortWithValidation(int[] array) {
        // 檢查 null 參考
        Objects.requireNonNull(array, "Array cannot be null");
        
        // 檢查數組大小
        if (array.length <= 1) {
            return; // 無需排序
        }
        
        // 檢查整數溢出風險
        if (array.length > Integer.MAX_VALUE / 2) {
            throw new IllegalArgumentException("Array too large for merge sort");
        }
        
        mergeSortHelper(array);
    }
    
    /**
     * 2. 內存優化
     */
    public static void memoryOptimizedMergeSort(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }
        
        // 重用輔助數組，避免重複分配
        int[] auxiliary = new int[array.length];
        mergeSortWithAuxiliary(array, auxiliary, 0, array.length - 1);
    }
    
    /**
     * 3. 異常處理
     */
    public static void robustMergeSort(int[] array) {
        try {
            validateArray(array);
            
            if (array.length > MEMORY_THRESHOLD) {
                // 大數組使用外部排序
                handleLargeArray(array);
            } else {
                // 正常內存排序
                ClassicMergeSort.mergeSort(array);
            }
            
        } catch (OutOfMemoryError e) {
            // 內存不足時的備用策略
            System.gc();
            fallbackToIterativeSort(array);
        } catch (Exception e) {
            logger.error("Merge sort failed", e);
            throw new SortingException("Failed to sort array", e);
        }
    }
    
    /**
     * 4. 性能監控
     */
    public static void monitoredMergeSort(int[] array, String context) {
        long startTime = System.nanoTime();
        long startMemory = getUsedMemory();
        
        try {
            ClassicMergeSort.mergeSort(array);
        } finally {
            long endTime = System.nanoTime();
            long endMemory = getUsedMemory();
            
            recordMetrics(context, array.length, 
                         endTime - startTime, endMemory - startMemory);
        }
    }
    
    // 輔助方法實現省略
    private static void validateArray(int[] array) { /* ... */ }
    private static void handleLargeArray(int[] array) { /* ... */ }
    private static void fallbackToIterativeSort(int[] array) { /* ... */ }
    private static long getUsedMemory() { return 0; /* ... */ }
    private static void recordMetrics(String context, int size, long time, long memory) { /* ... */ }
    
    private static final int MEMORY_THRESHOLD = 10_000_000;
    private static final java.util.logging.Logger logger = 
        java.util.logging.Logger.getLogger(MergeSortBestPractices.class.getName());
}

12.2 常見反模式和解決方案

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

/**
 * MergeSort 反模式和解決方案
 */
public class MergeSortAntiPatterns {
    
    /**
     * 反模式 1：重複分配輔助數組
     * 問題：每次遞歸都創建新的輔助數組
     */
    public static void badMergeSortWithRepeatedAllocation(int[] array, int start, int end) {
        if (start >= end) return;
        
        int mid = start + (end - start) / 2;
        
        // ❌ 錯誤：每次都創建新數組
        int[] leftAux = new int[mid - start + 1];
        int[] rightAux = new int[end - mid];
        
        // 遞歸調用...
    }
    
    /**
     * 解決方案：重用輔助數組
     */
    public static void goodMergeSortWithSharedAuxiliary(int[] array) {
        int[] auxiliary = new int[array.length]; // 只分配一次
        mergeSortHelper(array, auxiliary, 0, array.length - 1);
    }
    
    /**
     * 反模式 2：不檢查整數溢出
     * 問題：(start + end) 可能溢出
     */
    public static void badMidCalculation(int start, int end) {
        // ❌ 錯誤：可能整數溢出
        int mid = (start + end) / 2;
    }
    
    /**
     * 解決方案：安全的中點計算
     */
    public static void goodMidCalculation(int start, int end) {
        // ✅ 正確：避免溢出
        int mid = start + (end - start) / 2;
    }
    
    /**
     * 反模式 3：忽略小數組優化
     * 問題：對所有大小都使用遞歸
     */
    public static void badNoOptimization(int[] array, int start, int end) {
        if (start >= end) return;
        
        // ❌ 對小數組也使用複雜的遞歸邏輯
        int mid = start + (end - start) / 2;
        badNoOptimization(array, start, mid);
        badNoOptimization(array, mid + 1, end);
        // merge...
    }
    
    /**
     * 解決方案：小數組使用插入排序
     */
    public static void goodWithOptimization(int[] array, int start, int end) {
        // ✅ 小數組使用更高效的算法
        if (end - start + 1 <= INSERTION_SORT_THRESHOLD) {
            insertionSort(array, start, end);
            return;
        }
        
        int mid = start + (end - start) / 2;
        goodWithOptimization(array, start, mid);
        goodWithOptimization(array, mid + 1, end);
        // merge...
    }
    
    /**
     * 反模式 4：不處理已排序情況
     * 問題：即使已排序也執行合併
     */
    public static void badAlwaysMerge(int[] array, int start, int mid, int end) {
        // ❌ 總是執行合併，即使已經排序
        merge(array, start, mid, end);
    }
    
    /**
     * 解決方案：檢查是否需要合併
     */
    public static void goodConditionalMerge(int[] array, int start, int mid, int end) {
        // ✅ 檢查是否已經排序
        if (array[mid] <= array[mid + 1]) {
            return; // 已排序，跳過合併
        }
        merge(array, start, mid, end);
    }
    
    /**
     * 反模式 5：忽略穩定性
     * 問題：使用 < 而不是 <= 比較相等元素
     */
    public static void badInstableMerge(int[] array, int[] aux, int i, int j, int k) {
        // ❌ 使用 < 會破壞穩定性
        if (aux[i] < aux[j]) {
            array[k] = aux[i++];
        } else {
            array[k] = aux[j++];
        }
    }
    
    /**
     * 解決方案：保持穩定性
     */
    public static void goodStableMerge(int[] array, int[] aux, int i, int j, int k) {
        // ✅ 使用 <= 保持穩定性
        if (aux[i] <= aux[j]) {
            array[k] = aux[i++];
        } else {
            array[k] = aux[j++];
        }
    }
    
    private static final int INSERTION_SORT_THRESHOLD = 7;
    
    // 輔助方法
    private static void insertionSort(int[] array, int start, int end) { /* ... */ }
    private static void merge(int[] array, int start, int mid, int end) { /* ... */ }
}

13. 實際應用案例 (Real-world Applications)

13.1 金融交易系統

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

/**
 * 金融交易排序系統
 * 處理大量交易記錄的高性能排序
 */
@Service
public class FinancialTransactionSortingService {
    
    /**
     * 交易記錄類
     */
    public static class Transaction {
        private final String transactionId;
        private final LocalDateTime timestamp;
        private final BigDecimal amount;
        private final String currency;
        private final TransactionType type;
        
        // 構造函數和 getter 方法省略
        
        public enum TransactionType {
            BUY, SELL, TRANSFER, DIVIDEND
        }
    }
    
    /**
     * 多維度交易排序
     */
    public List<Transaction> sortTransactionsByMultipleCriteria(
            List<Transaction> transactions) {
        
        Transaction[] array = transactions.toArray(new Transaction[0]);
        
        // 多級排序：時間 -> 金額 -> 類型
        Comparator<Transaction> comparator = 
            Comparator.comparing(Transaction::getTimestamp)
                      .thenComparing(Transaction::getAmount)
                      .thenComparing(Transaction::getType);
        
        ModernMergeSort.mergeSort(array, comparator);
        
        return Arrays.asList(array);
    }
    
    /**
     * 高頻交易排序（微秒級性能要求）
     */
    public void sortHighFrequencyTrades(Transaction[] trades) {
        // 對高頻交易使用優化版本
        if (trades.length > 100_000) {
            ParallelMergeSort.parallelMergeSort(trades, 
                Comparator.comparing(Transaction::getTimestamp));
        } else {
            OptimizedMergeSort.optimizedMergeSort(trades,
                Comparator.comparing(Transaction::getTimestamp));
        }
    }
}

13.2 日誌分析系統

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

/**
 * 大規模日誌排序分析系統
 */
@Service
public class LogAnalysisService {
    
    /**
     * 日誌條目類
     */
    public static class LogEntry {
        private final LocalDateTime timestamp;
        private final String level;
        private final String source;
        private final String message;
        private final String threadId;
        
        // 構造函數和方法省略
    }
    
    /**
     * 時間範圍日誌排序
     */
    public List<LogEntry> sortLogsByTimeRange(
            List<LogEntry> logs, 
            LocalDateTime startTime, 
            LocalDateTime endTime) {
        
        return logs.parallelStream()
                  .filter(log -> isInTimeRange(log, startTime, endTime))
                  .sorted(Comparator.comparing(LogEntry::getTimestamp))
                  .collect(Collectors.toList());
    }
    
    /**
     * 多文件日誌合併排序
     */
    public void mergeAndSortLogFiles(List<String> logFiles, String outputFile) 
            throws IOException {
        
        // 使用外部排序處理大型日誌文件
        List<String> sortedChunks = new ArrayList<>();
        
        for (String logFile : logFiles) {
            String sortedChunk = sortSingleLogFile(logFile);
            sortedChunks.add(sortedChunk);
        }
        
        mergeLogChunks(sortedChunks, outputFile);
    }
    
    private String sortSingleLogFile(String logFile) throws IOException {
        // 讀取、解析、排序單個日誌文件
        List<LogEntry> logs = parseLogFile(logFile);
        
        LogEntry[] array = logs.toArray(new LogEntry[0]);
        ModernMergeSort.mergeSort(array, 
            Comparator.comparing(LogEntry::getTimestamp));
        
        String outputFile = logFile + ".sorted";
        writeLogFile(outputFile, Arrays.asList(array));
        
        return outputFile;
    }
    
    // 輔助方法省略
    private List<LogEntry> parseLogFile(String fileName) { return null; }
    private void writeLogFile(String fileName, List<LogEntry> logs) { }
    private void mergeLogChunks(List<String> chunks, String output) { }
    private boolean isInTimeRange(LogEntry log, LocalDateTime start, LocalDateTime end) { return false; }
}

13.3 搜索引擎索引排序

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111

/**
 * 搜索引擎索引排序系統
 */
@Service
public class SearchIndexSortingService {
    
    /**
     * 文檔索引項
     */
    public static class IndexEntry {
        private final String term;
        private final int documentId;
        private final double relevanceScore;
        private final int frequency;
        
        // 構造函數和方法省略
    }
    
    /**
     * 索引排序策略
     */
    public enum SortStrategy {
        BY_TERM,           // 按詞彙排序
        BY_RELEVANCE,      // 按相關性排序
        BY_FREQUENCY,      // 按頻率排序
        BY_DOCUMENT_ID     // 按文檔ID排序
    }
    
    /**
     * 大規模索引排序
     */
    public void sortSearchIndex(IndexEntry[] entries, SortStrategy strategy) {
        Comparator<IndexEntry> comparator = getComparatorForStrategy(strategy);
        
        if (entries.length > 1_000_000) {
            // 大規模索引使用並行排序
            ParallelMergeSort.parallelMergeSort(entries, comparator);
        } else {
            ModernMergeSort.mergeSort(entries, comparator);
        }
    }
    
    /**
     * 多級索引排序
     */
    public void sortIndexWithMultipleCriteria(IndexEntry[] entries) {
        // 複合排序：相關性 -> 頻率 -> 詞彙
        Comparator<IndexEntry> comparator = 
            Comparator.comparing(IndexEntry::getRelevanceScore).reversed()
                      .thenComparing(IndexEntry::getFrequency).reversed()
                      .thenComparing(IndexEntry::getTerm);
        
        ModernMergeSort.mergeSort(entries, comparator);
    }
    
    /**
     * 增量索引更新排序
     */
    public IndexEntry[] mergeIncrementalUpdates(
            IndexEntry[] existingIndex, 
            IndexEntry[] newEntries) {
        
        // 先排序新條目
        ModernMergeSort.mergeSort(newEntries, 
            Comparator.comparing(IndexEntry::getTerm));
        
        // 合併兩個已排序的索引
        return mergeSortedIndexes(existingIndex, newEntries);
    }
    
    private Comparator<IndexEntry> getComparatorForStrategy(SortStrategy strategy) {
        switch (strategy) {
            case BY_TERM:
                return Comparator.comparing(IndexEntry::getTerm);
            case BY_RELEVANCE:
                return Comparator.comparing(IndexEntry::getRelevanceScore).reversed();
            case BY_FREQUENCY:
                return Comparator.comparing(IndexEntry::getFrequency).reversed();
            case BY_DOCUMENT_ID:
                return Comparator.comparing(IndexEntry::getDocumentId);
            default:
                return Comparator.comparing(IndexEntry::getTerm);
        }
    }
    
    private IndexEntry[] mergeSortedIndexes(IndexEntry[] existing, IndexEntry[] newEntries) {
        // 實現兩個已排序數組的合併邏輯
        IndexEntry[] result = new IndexEntry[existing.length + newEntries.length];
        
        int i = 0, j = 0, k = 0;
        Comparator<IndexEntry> comparator = Comparator.comparing(IndexEntry::getTerm);
        
        while (i < existing.length && j < newEntries.length) {
            if (comparator.compare(existing[i], newEntries[j]) <= 0) {
                result[k++] = existing[i++];
            } else {
                result[k++] = newEntries[j++];
            }
        }
        
        while (i < existing.length) {
            result[k++] = existing[i++];
        }
        
        while (j < newEntries.length) {
            result[k++] = newEntries[j++];
        }
        
        return result;
    }
}

14.1 MergeSort 的核心價值

MergeSort 作為一種經典的分治算法，在現代軟件開發中依然具有重要價值：

  1. 穩定性保證：對於需要保持相等元素相對順序的場景至關重要
  2. 可預測性能：O(n log n) 的時間複雜度在所有情況下都保持一致
  3. 並行友好：天然適合並行處理和分散式計算
  4. 外部排序：適用於處理無法完全載入內存的大型數據集

14.2 現代化發展趨勢

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

/**
 * MergeSort 的現代化趨勢和未來發展
 */
public class FutureMergeSortTrends {
    
    /**
     * 1. GPU 加速排序
     */
    public static void gpuAcceleratedMergeSort(int[] array) {
        // 利用 GPU 並行計算能力
        // 需要 CUDA 或 OpenCL 支持
        if (isGpuAvailable() && array.length > GPU_THRESHOLD) {
            executeOnGpu(array);
        } else {
            ParallelMergeSort.parallelMergeSort(array);
        }
    }
    
    /**
     * 2. 機器學習優化
     */
    public static void mlOptimizedMergeSort(int[] array, DataCharacteristics characteristics) {
        // 根據數據特徵選擇最優策略
        SortingStrategy strategy = MLSortingOptimizer.predictOptimalStrategy(characteristics);
        
        switch (strategy) {
            case PARALLEL:
                ParallelMergeSort.parallelMergeSort(array);
                break;
            case OPTIMIZED:
                OptimizedMergeSort.optimizedMergeSort(array);
                break;
            case HYBRID:
                HybridMergeSort.adaptiveMergeSort(array);
                break;
        }
    }
    
    /**
     * 3. 量子計算排序
     */
    public static void quantumInspiredMergeSort(int[] array) {
        // 量子啟發的排序算法
        // 利用量子疊加和糾纏特性
        if (array.length > QUANTUM_THRESHOLD) {
            QuantumSortingSimulator.quantumMergeSort(array);
        } else {
            ClassicMergeSort.mergeSort(array);
        }
    }
    
    /**
     * 4. 自適應閾值優化
     */
    public static void adaptiveThresholdMergeSort(int[] array) {
        // 動態調整各種閾值參數
        AdaptiveParameters params = PerformanceProfiler.analyzeAndOptimize(array);
        
        ConfigurableMergeSort.mergeSort(array, params);
    }
    
    // 模擬的輔助類和方法
    private static boolean isGpuAvailable() { return false; }
    private static void executeOnGpu(int[] array) { }
    
    private static final int GPU_THRESHOLD = 1_000_000;
    private static final int QUANTUM_THRESHOLD = 10_000_000;
    
    // 模擬的類型
    public enum SortingStrategy { PARALLEL, OPTIMIZED, HYBRID }
    public static class DataCharacteristics { }
    public static class AdaptiveParameters { }
    public static class MLSortingOptimizer {
        public static SortingStrategy predictOptimalStrategy(DataCharacteristics dc) { return SortingStrategy.OPTIMIZED; }
    }
    public static class QuantumSortingSimulator {
        public static void quantumMergeSort(int[] array) { ClassicMergeSort.mergeSort(array); }
    }
    public static class PerformanceProfiler {
        public static AdaptiveParameters analyzeAndOptimize(int[] array) { return new AdaptiveParameters(); }
    }
    public static class ConfigurableMergeSort {
        public static void mergeSort(int[] array, AdaptiveParameters params) { ClassicMergeSort.mergeSort(array); }
    }
}

14.3 企業級最佳實踐總結

  1. 性能監控：實施全面的性能指標收集和分析
  2. 資源管理：智能的內存和 CPU 資源使用策略
  3. 錯誤處理：強大的異常處理和故障恢復機制
  4. 可擴展性：設計支持水平和垂直擴展的排序系統
  5. 安全性：確保數據處理過程的安全性和隱私保護

14.4 學習建議

對於深入學習 MergeSort 的開發者，建議：

  1. 理論基礎：深入理解分治法和遞歸的數學原理
  2. 實踐經驗：在不同場景下實際應用和優化算法
  3. 性能調優：學習使用各種性能分析工具
  4. 並行計算：掌握多線程和分散式計算技術
  5. 系統設計：了解大規模系統中的排序需求和挑戰

合久必分，分久必合 - 這不僅是 MergeSort 的核心思想，也是軟件系統設計的重要原則。通過不斷的分解和合併，我們能夠處理任何複雜度的問題，構建出健壯、高效的企業級應用系統。

本文檔提供了 MergeSort 的全面解析，從基礎理論到企業應用，涵蓋了現代 Java 開發中所需的各個方面。希望能夠幫助開發者深入理解和有效應用這一經典算法。

留言討論