// tmp::Sort — C++14 TMP Introsort
// Phase 1: IntroSort (QuickSort + HeapSort fallback), skip small segments
// Phase 2: Single-pass Insertion Sort over whole array (guarded only)
// Correctness first, then optimization

#include <utility>
#include <type_traits>
#include <cstdio>
#include <cstdlib>
#include <algorithm>

namespace tmp {

// ============================================================
// § 1  TMP 基礎工具
// ============================================================
template<int V>  struct Int  { static constexpr int  value = V; };
template<bool V> struct Bool { static constexpr bool value = V; };

template<int N> struct Log2 : Int<1 + Log2<N/2>::value> {};
template<>      struct Log2<1> : Int<0> {};
template<>      struct Log2<0> : Int<0> {};

template<bool C, typename T, typename F> struct If          { using type = F; };
template<typename T, typename F>         struct If<true,T,F>{ using type = T; };

// ============================================================
// § 2  Comparator 策略
// ============================================================
template<typename T>
struct Less    { bool operator()(const T& a, const T& b) const { return a < b; } };
template<typename T>
struct Greater { bool operator()(const T& a, const T& b) const { return a > b; } };

// ============================================================
// § 3  Median-of-3
//    排好 arr[lo] <= arr[mid] <= arr[hi]，pivot(=arr[mid])放到 arr[hi-1]
// ============================================================
template<typename Comp>
struct MedianOf3 {
    template<typename T>
    static void apply(T* a, int lo, int mid, int hi, Comp cmp) {
        if (cmp(a[mid], a[lo]))  std::swap(a[mid], a[lo]);
        if (cmp(a[hi],  a[lo]))  std::swap(a[hi],  a[lo]);
        if (cmp(a[hi],  a[mid])) std::swap(a[hi],  a[mid]);
        std::swap(a[mid], a[hi-1]);   // pivot → a[hi-1]
    }
};

// ============================================================
// § 4  3-way Partition
//    pivot 已在 a[hi-1]；哨兵 a[lo]<=pivot, a[hi]>=pivot
//    結果：a[lt..gt]==pivot
// ============================================================
template<typename Comp>
struct Partition3Way {
    template<typename T>
    static std::pair<int,int> run(T* a, int lo, int hi, Comp cmp) {
        T pivot = a[hi-1];
        int lt = lo, gt = hi-1, i = lo;
        while (i <= gt) {
            if      (cmp(a[i], pivot)) std::swap(a[lt++], a[i++]);
            else if (cmp(pivot, a[i])) std::swap(a[i],    a[gt--]);
            else                       ++i;
        }
        return {lt, gt};
    }
};

// ============================================================
// § 5  Heap Sort（depth 超標 fallback）
// ============================================================
template<typename Comp>
struct HeapSort {
    template<typename T>
    static void siftDown(T* a, int i, int n, int base, Comp cmp) {
        T tmp = std::move(a[base+i]);
        for (;;) {
            int c = 2*i+1;
            if (c >= n) break;
            if (c+1 < n && cmp(a[base+c], a[base+c+1])) ++c;
            if (!cmp(tmp, a[base+c])) break;
            a[base+i] = std::move(a[base+c]);
            i = c;
        }
        a[base+i] = std::move(tmp);
    }
    template<typename T>
    static void sort(T* a, int lo, int hi, Comp cmp) {
        int n = hi-lo+1;
        for (int i = n/2-1; i >= 0; --i) siftDown(a, i, n, lo, cmp);
        for (int i = n-1;   i > 0;  --i) {
            std::swap(a[lo], a[lo+i]);
            siftDown(a, 0, i, lo, cmp);
        }
    }
};

// ============================================================
// § 6  Insertion Sort（guarded，有邊界保護）
// ============================================================
template<typename Comp>
struct InsertionSort {
    template<typename T>
    static void sort(T* a, int lo, int hi, Comp cmp) {
        for (int i = lo+1; i <= hi; ++i) {
            T key = std::move(a[i]);
            int j = i-1;
            while (j >= lo && cmp(key, a[j])) {
                a[j+1] = std::move(a[j]); --j;
            }
            a[j+1] = std::move(key);
        }
    }
};

// ============================================================
// § 7  IntroSort 核心
// ============================================================
template<typename Comp, int THRESHOLD>
struct IntroCore {
    template<typename T>
    static void sort(T* a, int lo, int hi, int depth, Comp cmp) {
        while (hi - lo + 1 > THRESHOLD) {
            if (depth == 0) {
                HeapSort<Comp>::sort(a, lo, hi, cmp);
                return;
            }
            --depth;
            int mid = lo + (hi-lo)/2;
            MedianOf3<Comp>::apply(a, lo, mid, hi, cmp);
            auto p = Partition3Way<Comp>::run(a, lo, hi, cmp);
            // 尾遞迴：遞迴較小側
            if (p.first - lo < hi - p.second) {
                sort(a, lo,          p.first-1,  depth, cmp);
                lo = p.second + 1;
            } else {
                sort(a, p.second+1, hi,           depth, cmp);
                hi = p.first - 1;
            }
        }
        // 小段落下給 Phase 2
    }
};

// ============================================================
// § 8  對外介面：tmp::Sort<THRESHOLD>
// ============================================================
template<int THRESHOLD = 16>
struct Sort {
    static int depthLimit(int n) {
        int d = 0; while (n > 1) { n >>= 1; ++d; } return d * 2;
    }

    // --- sort(arr, n) ---
    template<typename T>
    static void sort(T* a, int n) { sort(a, n, Less<T>{}); }

    // --- sort(arr, n, comp) ---
    template<typename T, typename Comp>
    static void sort(T* a, int n, Comp cmp) {
        if (n <= 1) return;
        using Core = IntroCore<Comp, THRESHOLD>;
        // Phase 1：QuickSort，跳過小片段
        Core::sort(a, 0, n-1, depthLimit(n), cmp);
        // Phase 2：一次 Insertion Sort 收尾（guarded，正確且簡單）
        InsertionSort<Comp>::sort(a, 0, n-1, cmp);
    }

    // --- sort(first, last) ---
    template<typename T>
    static void sort(T* first, T* last) {
        sort(first, static_cast<int>(last - first));
    }

    // --- sort(first, last, comp) ---
    template<typename T, typename Comp>
    static void sort(T* first, T* last, Comp cmp) {
        sort(first, static_cast<int>(last - first), cmp);
    }
};

} // namespace tmp

// ============================================================
// § 9  Demo
// ============================================================
static bool verify(const int* a, const int* b, int n) {
    for (int i = 0; i < n; ++i) if (a[i] != b[i]) return false;
    return true;
}
static void test(const char* name, int* a, int* r, int n) {
    std::sort(r, r+n);
    tmp::Sort<>::sort(a, n);
    printf("[%s] n=%-8d  %s\n", verify(a,r,n)?"PASS":"FAIL", n, name);
}
static void show(const char* lbl, const int* a, int n) {
    printf("  %-30s", lbl);
    int s = n<20?n:20;
    for(int i=0;i<s;i++) printf("%d%c",a[i]," \n"[i==s-1]);
    if(n>20) printf(" ...(n=%d)\n",n);
}

int main() {
    srand(42);
    printf("=== tmp::Sort<> — Introsort TMP ===\n\n");

    // 1. 基本
    { int a[]={5,3,8,1,9,2,7,4,6,0},r[]={5,3,8,1,9,2,7,4,6,0};
      test("random 10",a,r,10); show("→",a,10); }

    // 2. 邊界：n=0,1,2
    { int a1[]={}, r1[]={};          test("n=0",a1,r1,0); }
    { int a2[]={7}, r2[]={7};        test("n=1",a2,r2,1); }
    { int a3[]={5,2}, r3[]={5,2};    test("n=2",a3,r3,2); }

    // 3. 已排序 升/降
    { static int a[10000],r[10000];
      for(int i=0;i<10000;i++) a[i]=r[i]=i;
      test("sorted asc 10000",a,r,10000);
      for(int i=0;i<10000;i++) a[i]=r[i]=9999-i;
      test("sorted desc 10000",a,r,10000); }

    // 4. 全部相同
    { static int a[100000],r[100000];
      for(int i=0;i<100000;i++) a[i]=r[i]=42;
      test("all equal 100000",a,r,100000); }

    // 5. 大量重複（3-way partition 優勢）
    { static int a[100000],r[100000];
      for(int i=0;i<100000;i++) a[i]=r[i]=rand()%100;
      test("100 vals in 100000",a,r,100000); }

    // 6. 大陣列隨機
    { static int a[1000000],r[1000000];
      for(int i=0;i<1000000;i++) a[i]=r[i]=rand();
      test("random 1000000",a,r,1000000); }

    // 7. 自訂 Comp（降序）
    printf("\n--- Descending ---\n");
    { int a[]={3,1,4,1,5,9,2,6,5,3};
      tmp::Sort<>::sort(a,10,tmp::Greater<int>{});
      show("desc:",a,10); }

    // 8. 指標範圍介面
    printf("--- Pointer range ---\n");
    { int a[]={9,1,8,2,7,3,6,4,5,0};
      tmp::Sort<>::sort(a,a+10);
      show("range:",a,10); }

    // 9. 自訂 struct + lambda
    printf("--- Struct + lambda ---\n");
    { struct Pt { int x,y; };
      Pt pts[]={{3,1},{1,5},{2,2},{1,1},{3,0}};
      tmp::Sort<>::sort(pts,5,[](const Pt&a,const Pt&b){
          return a.x!=b.x?a.x<b.x:a.y<b.y; });
      for(int i=0;i<5;i++) printf("(%d,%d)%c",pts[i].x,pts[i].y," \n"[i==4]); }

    // 10. 不同 THRESHOLD
    printf("--- THRESHOLD=4 ---\n");
    { static int a[50000],r[50000];
      for(int i=0;i<50000;i++) a[i]=r[i]=rand();
      std::sort(r,r+50000);
      tmp::Sort<4>::sort(a,50000);
      printf("[%s] THRESHOLD=4 n=50000\n",verify(a,r,50000)?"PASS":"FAIL"); }

    // 11. 互動
    printf("\n--- Interactive ---\n");
    { int n; scanf("%d",&n);
      static int a[1000000];
      for(int i=0;i<n;i++) scanf("%d",&a[i]);
      tmp::Sort<>::sort(a,n);
      for(int i=0;i<n;i++) printf("%d%c",a[i]," \n"[i==n-1]); }

    return 0;
}