ArrayList 是 Java 中一個動態數組數據結構，隨著元素的添加，ArrayList 在需要時會自動擴容。ArrayList 的排序原理主要依賴于 Collections.sort() 方法，這個方法對 ArrayList 進行原地排序（即直接修改原列表，而不是創建一個新的排序列表）。
Collections.sort() 方法使用的排序算法是 TimSort。TimSort 是一種穩定的、自適應的排序算法，主要結合了歸并排序（Merge Sort）和插入排序（Insertion Sort）的優點。以下是 TimSort 算法在 Java 中的實現原理：
- 分區（Partitioning）：首先，TimSort 將輸入的列表劃分為一系列小的區塊（Run）。每個區塊內的元素可以視為已排序，且區塊之間的順序無關緊要。區塊的大小取決于多種因素，如輸入數據的特點和排序算法的性能。
- 歸并排序（Merge Sort）：接下來，TimSort 對相鄰的區塊進行歸并操作。歸并排序是一種分治算法，它將兩個有序的區塊合并成一個更大的有序區塊。這個過程會遞歸地進行，直到整個列表被合并為一個大的有序區塊。
- 插入排序（Insertion Sort）：在歸并過程中，當處理較小的區塊時，插入排序的性能通常優于歸并排序。因此，TimSort 在適當的時候會將這些小區塊視為已排序，并使用插入排序將它們合并到前面的已排序區塊中。
- 穩定性（Stability）：TimSort 是一種穩定的排序算法，這意味著相等的元素在排序后保持原來的相對順序。這是歸并排序的一個特性，也是 TimSort 在某些應用場景中比快速排序更受歡迎的原因之一。
總之，ArrayList 的排序原理主要依賴于 TimSort 算法，該算法通過分區、歸并排序和插入排序等步驟對列表進行原地排序。
