NikolaevMisha/5.3/new/new

/*


Дан массив неотрицательных целых 64-разрядных чисел. Количество чисел не больше 1000000. Отсортировать массив методом MSD по битам (бинарный QuickSort).
*/

#include <iostream>
#include <vector>

void Partition(std::vector<long long>& A,int start ,int finish ,int i) // бинарный QuickSort
{
    if(i == -1)
    {
        return;
    }
    int localStart = start;
    int localFinish = finish;
    while(localStart <= localFinish)
    {
        for(;localStart <= finish && (A[localStart] >> i) % 2 == 0 ; ++ localStart) {}

        for(;localFinish >= start && (A[localFinish] >> i) % 2 == 1 ; --localFinish) {}

        if(localStart < localFinish)
        {
            std::swap(A[localStart] , A[localFinish]);
            ++localStart;
            --localFinish;
        }
    }
    if(localFinish > start)
    {
        Partition(A , start , localFinish , i - 1);
    }
    if(localStart < finish)
    {
        Partition(A , localStart , finish , i - 1);
    }



}

int main()
{
    int n;
    std::cin >> n;
    std::vector<long long> A(n);
    for(int i = 0; i < n; ++i)
    {
        std::cin >> A[i];
    }

    Partition(A, 0 , n - 1, 63);
    for(int i = 0; i < n; ++i)
    {
        std::cout << A[i] << " ";
    }
    std::cout << '\n';
    return 0;
}