Какая сложность сортировки массива

Сортировка массива в Java (например, с помощью Arrays.sort()) имеет сложность:

• O(n log n) для примитивных типов (используется алгоритм TimSort)
• O(n log n) для объектов (используется модифицированный MergeSort)

Пример:

int[] arr = {5, 2, 9, 1};
Arrays.sort(arr);  // O(n log n)

В худшем случае (крайне редком) сложность может достигать O(n²), но на практике это почти не встречается. Для небольших массивов (до ~47 элементов) Java использует InsertionSort с O(n²), но это незначительно влияет на общую производительность.