Тут 2 независимые задачи:
1) разобраться с нейросетями, тут язык не имеет большого значения, можно курс по ним на курсере/степике пройти или DLB почитать;
2) начать их писать на C++, тут основные фреймворки это torch и tensorflow, у второго точно есть C++ API.
C++ - довольно специфический язык, его действительно тяжело выучить самостоятельно, занимаясь по книгам.
Я очень рекомендую обратить внимание на специализацию от ребят из Яндекса: https://www.coursera.org/specializations/c-plus-pl...
То, что вы написали, называется сортировка подсчётом. Сложность действительно O(n), поскольку вы проходите по исходному массиву всего 1 раз.
Вы также проходите 2 раза и по массиву фиксированной длины (65536).
Общий анализ выглядит следующим образом:
65536 (заполнение нулями) + N (проход по исходному массиву для подсчёта элементов) + 65536 (проход по массиву счётчиков для записи в выходной, теперь уже отсортированный массив) = 2*65536 + N = O(N + 2*65536) = O(N).
В случае сортировки вставками вы в худшем случае делаете N операций (оценка грубая) для каждого из N элементов исходного массива: N*N=N^2=O(N^2).