马掌门在研究阴阳互相转化的过程中发明了一种有趣的排序算法，他将这种排序算法命名为混元形意排序法。如果我们用C++实现该算法，可以得到以下的代码。

#define N 100009
int tmp[N];
void change(int arr[], int begin, int end)
{
    if (begin >= end)
        return;
    int mid = (begin + end) / 2, size = 0;
    for (int i = mid + 1; i <= end; ++i)
        tmp[++size] = arr[i];
    for (int i = begin; i <= mid; ++i)
        tmp[++size] = arr[i];
    for (int i = 0; i < size; ++i)
        arr[i + begin] = tmp[i + 1];
}

void sort(int arr[], int begin, int end)
{
    if (begin >= end)
        return;
    int mid = (begin + end) / 2;
    sort(arr, begin, mid);
    sort(arr, mid + 1, end);
    if (arr[begin] > arr[mid + 1])
        change(arr, begin, end);
}