原创排序算法 SplitMergeSort：一种非二分、非传统分治的全新排序思路

OriginalSort-Algorithm

原创拆分-归并排序算法（SplitMergeSort），由zuimengyu设计.
一种全新思路的递归排序算法，原创结构，非传统分治/二分/快排体系。
该算法通过贪心递增拆分策略，将数组拆分为自然递增序列 A 与待递归序列 B，仅对 B 进行递归处理，最后通过双指针归并完成排序。
核心特点
完全独立原创
结构清晰，逻辑简单但效率可优化至 O(n log n)
回溯阶段采用双指针线性归并，时间复杂度 O(n)

时间复杂度

• 最好情况：O(n)（数组已有序）
• 最坏情况：O(n²)（完全逆序）
• 平均情况：O(n²)

import java.util.ArrayList;
import java.util.List;

public class SplitMergeSort {

public static void main(String[] args) { List<Integer> arr = new ArrayList<>(); arr.add(5); arr.add(8); arr.add(16); arr.add(7); arr.add(2); arr.add(19); arr.add(4); arr.add(18); arr.add(79); arr.add(25); arr.add(49); arr.add(33); arr.add(27); arr.add(18); System.out.println("排序前：" + arr); List<Integer> sorted = yourSort(arr); System.out.println("排序后：" + sorted); } public static List<Integer> yourSort(List<Integer> arr) { if (arr == null || arr.size() <= 1) { return new ArrayList<>(arr); } List<Integer> A = new ArrayList<>(); List<Integer> B = new ArrayList<>(); for (int num : arr) { if (A.isEmpty()) { A.add(num); } else { if (num < A.get(A.size() - 1)) { B.add(num); } else { A.add(num); } } } List<Integer> sortedB = yourSort(B); return mergeTwoSorted(A, sortedB); } private static List<Integer> mergeTwoSorted(List<Integer> a, List<Integer> b) { List<Integer> res = new ArrayList<>(); int i = 0, j = 0; while (i < a.size() && j < b.size()) { if (a.get(i) < b.get(j)) { res.add(a.get(i++)); } else { res.add(b.get(j++)); } } while (i < a.size()) res.add(a.get(i++)); while (j < b.size()) res.add(b.get(j++)); return res; }

}