// low: 起点index
// count: scope的大小, 当scope是1时说明全部处理完成, 终止
// direction: 升序/降序
// algo
// 1. TODO: review
void bitonic_sort(int[] arr, int low, int count, int direction) {
    if (count <= 1)
        return;

    int k = count / 2;
    // direction = 1, 升序
    bitonic_sort(arr, low, k, 1);
    // direction = 0, 降序
    bitonic_sort(arr, low + k, k, 0);
    bitonic_merge(arr, low, count, direction);
}

void bitonic_merge(int[] arr, int low, int count, int direction) {
    if (count <= 1)
        return;

    int k = count / 2;
    for (int i = low; i < low + k; i++) {
        // NOTE: 先merge再递归
        if (direction = (arr[i] > arr[i + k])) {
            swap(arr[i], arr[i+k]);
        }
        // NOTE: 先merge再递归
        // 先粗粒度merge, 再递归细粒度merge
        bitonic_merge(arr, low, k, direction);
        bitonic_merge(arr, low + k, k, direction);
    }

}