int* genArr(int len, int range){
    // 记得用完要把它 free 掉：
    int* arr = (int*)malloc(sizeof(int) * len);
    for(int i = 0; i < len; i++) arr[i] = rand() % range;
    return arr;
}

void printArr(int* arr, int len){
    for(int i = 0; i < len; i++) cout<<arr[i]<<" ";
    cout<<endl;
}

void swap(int* a, int* b){
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void bubbleSort(int* arr, int len){
    for(int i = 0; i < len; i++)
        for(int j = i; j < len; j++)
            if(arr[i] > arr[j])
                swap(&arr[i], &arr[j]);
}

void insertSort(int* arr, int len){
    for(int i = 1; i < len; i++){
        int cur = arr[i], j = i - 1;
        while(j >= 0 && arr[j] > cur)
            // Attention that arr[j + 1] = arr[j--] is wrong.
            arr[j-- + 1] = arr[j];
        arr[j + 1] = cur;
    }
}

void shellSort(int* arr, int len){
    for(int gap = len >> 1; gap > 0; gap >>= 1){
        for(int i = gap; i < len; i += gap){
            int cur = arr[i];
            int j = i - gap;
            while(j >= 0 && arr[j] > cur){
                arr[j + gap] = arr[j];
                j -= gap;
            }
            arr[j + gap] = cur;
        }
    }
}

int* mergeSort(int* arr1, int len1, int* arr2, int len2){
    int len = len1 + len2;
    int* arr = (int*)malloc(sizeof(int) * len);
    int pos1 = 0, pos = 0;
    while(pos < len){
        if(pos1 == len1) arr[pos++] = arr2[pos - pos1];
        else if(pos - pos1 == len2) arr[pos++] = arr1[pos1++];
        else arr[pos++] = arr1[pos1] > arr2[pos - pos1] ? arr2[pos - pos1] : arr1[pos1++];
    }
    return arr;
}

void qSort(int* arr, int l, int r){
    if(l >= r) return;
    int i = l, j = r;
    while(i < j){
        while(i < j && arr[j] >= arr[l]) j--;
        while(i < j && arr[i] <= arr[l]) i++;
        if(i < j) swap(&arr[i], &arr[j]);
    }
    swap(&arr[l], &arr[i]);
    qSort(arr, l, i - 1);
    qSort(arr, i + 1, r);
}