一大堆題目上線嘍 熱騰騰剛搬完的 2024 上機考、終局之戰、2025 小社賽和上機考都上線了，歡迎大家幫忙驗題，然後一五該請我拉麵了 --- by AaW
4589 . no std::sort（互動題）
Description
boron 最近看了一堆 sort 演算法可視化，甚至自己手搓了演算法可視化的扣，實在太強 Orz
但是他發現大家都只使用 std::sort 的黑魔法，都忘記自己學習演算法的初衷了，況且如此慢速且占空間的演算法在 sort 之神 boron 面前完全不堪一擊。因為 boron 會只需要 compare 和 swap 的演算法，不只空間複雜度是遠超其他人的 O(1)，常數也小的驚人。
然而 roy 太笨了，無法理解如此電神的領域，請你幫他設計出一個符合題目要求的算法吧
Input Format
此題不需要做輸入
Output Format
用互動題的方式輸出 (互動題說明放在 hints)
Sample Input 1
Sample Output 1
Hints
陣列為 0-based
針對測資 0-4，要求 compare 次數小於等於 $3 \times 10 ^ 5$，同時 swap 次數小於等於 $1.5 \times 10 ^ 5$
針對測資 5-9，要求 compare 次數小於等於 $1.5 \times 10 ^ 7$，同時 swap 次數小於等於 $8 \times 10 ^ 6$
如果超過這個限制，你會得到一個RE (也可能先TLE)，同時也要注意記憶體使用避免MLE
請注意，本題為互動題，請在程式碼加入一行#include "lib4589.h"，並且不需要實作main函式，程式只能寫在void sort_array()中，評測程式會呼叫你實作的 sort_array()。請不要有任何讀取輸入與輸出的操作，否則可能會發生各種不可預期的結果。
你能對陣列進行操作的方式只有幾種：
getArrayLength();，讀取陣列長度
compare(i, j);，回傳一個布林值，代表 $a[i]$ 是否小於 $a[j]$
swap(i, j);，將 $a[i]$ 與 $a[j]$ 做交換
finalize();，在排序完成後結束程式
以下是lib4589.h的內容:
int getArrayLength();
bool compare(int i, int j);
void swap(int i, int j);
void finalize();
Problem Source
https://youtu.be/R8CpE0nY930
裡面至少有三種演算法可以用
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | $N = 10 ^ 3$ | 5 |
| 2 | 2~4 | $N = 10 ^ 4$ | 30 |
| 3 | 5~9 | $N = 2 \times 10 ^ 5$ | 65 |