Сортировка разрядов в числе

[_D4rki_]

Условие задачи:

Числовые последовательности являются очень интересными математическими объектами. Рассмотрим последовательность, которая получается с помощью двух операций: удвоения и «сортировка разрядов». Последняя операция заключается в том, что разряды десятичной записи числа упорядочиваются по возрастанию. Например, число 5726 после сортировки превращается в 2567.
Первым членом последовательности является число 1, каждый следующий член получается умножением предыдущего на 2 и последующей сортировкой разрядов. Первые члены последовательности будут выглядеть так:
1, 2, 4, 8, 16, 23, 46, 29, 58, 116, 223, 446, 289, 578, 1156, …
Напишите программу, которая по номеру элемента последовательности вычисляет его значение.

Я написал правильно работающую программу, суть которой в том, что всё число поразрядно записывается в массив, и затем в массиве сортируются. Проблема в том, что если введенный номер элемента достаточно большой, то время работы программы очень долгое.

Как можно ускорить работу программы.

Вот мой код:

#include <iostream>
using namespace std;
int a[100];
template< class T >
void insertSort(T* a, int size)
{
    T tmp;
    for (int i = 1, j; i < size; ++i)
    {
        tmp = a[i];
        for (j = i - 1; j >= 0 && a[j] > tmp; --j)
            a[j + 1] = a[j];
        a[j + 1] = tmp;
    }
}
int sort(unsigned long long k) {
    int i = 1, c;
    while (k != 0) {
        a[i] = k % 10;
        k = k / 10;
        i++;
    }
    insertSort(a, i);
    k = 0;
    for (c = 1; c < i; c++) {
        k = k * 10 + a[c];
    }
    return k;
}
int main() {
    long long n;
    unsigned long long k;
    cin >> n;
    k = 1;
    for (int i = 1; i <= n - 1; i++) {
        k = k * 2;
        k = sort(k);
    }
    cout << k;
    return 0;
}