Tim Peter ရဲ့ Sort၊ TimSort

Java 24 မှာ Object Array တွေကို စီဖို့ Tim Peters Python သုံးပြီး ရေးခဲ့တဲ့ TimSort ကို သုံးပါတယ်။ TimSort ရဲ့ အလုပ်လုပ်ပုံက

// Facebook Feed Ranking လုပ်ငန်းစဉ်
class FacebookFeed {
    List<Post> getRankedFeed(User user) {
        List<Post> allPosts = collectPosts(user);

        // TimSort ရဲ့ အလုပ်လုပ်ပုံ:
        // 1. စီပြီးသား "runs" ရှာခြင်း
        allPosts = findNaturalRuns(allPosts);

        // 2. သေးငယ်သော runs များကို ပေါင်းခြင်း
        allPosts = mergeSmallRuns(allPosts);

        // 3. Optimized merging
        return optimizedMerge(allPosts);
    }
}

ဒီနေရာမှာ Peter ရဲ့ findNaturalRuns Algorithm နဲ့ ပါတ်သတ်ပြီးသူပြောခဲ့တာက Database log တွေကို TimeStamp တွေနဲ့ ရိုက်ကြတယ်။ Database record တွေကို primary key အနေနဲ့ သိမ်းကြတယ်။ ဒီ့အတွက် အဖြေက findNatualRuns ပါပဲတဲ့။ အောက်ဖေါ်ပြပါ ကုဒ်ကတော့ small runs တွေကို merge လုပ်တဲ့ပုံပါ။ Facebook ဥပမာပေးထားပါတယ်။

class FacebookFeedSorter {

    void processFeedUpdates() {
        // Initial: 100 posts (already sorted by time)
        Run run1 = new Run(0, 100);  // Old posts

        // User scrolls down: 20 new posts loaded
        Run run2 = new Run(100, 20); // New posts (timestamp sorted)

        // mergeSmallRuns လုပ်ငန်းစဉ်:
        stack.push(run1);
        stack.push(run2);

        // Check invariant:
        // run1.length = 100, run2.length = 20
        // Only one run in stack, no merge needed

        // More scrolling: 30 more posts
        Run run3 = new Run(120, 30);
        stack.push(run3);

        // Now stack has 3 runs: [100, 20, 30]
        // Check: 100 <= 20+30? 100 <= 50? ❌ (False - no merge)
        // Check: 20 <= 30? ✅ (True - invariant satisfied)
        // No merge needed!

        // User likes/shared - resort by engagement
        // New runs created, mergeSmallRuns efficiently merges them
    }
}

Tim က ရှိပြီးသား data တွေကို sorted ဖြစ်မဖြစ် အရင် detect လုပ်။ sort မဖြစ်သေးတာတွေကို small chunk အနေနဲ့ sort လုပ်။ ပြီးတော့ merge လုပ်တာပါ။