Есть ли способ внести простое изменение в этот алгоритм сортировки, чтобы он работал быстрее, чем квадратичное время?

Question

У меня есть следующий алгоритм сортировки, который работает в O (n ² ):

function sortingArray (U, n)
//S is the array and n is the size of the array
//1. First create a temp array and initialize to 0
for i = 0 to n - 1
  Temp[i] = 0
//2. This is where it gets skewed - essentially Temp is used to store indixes for the correct position of U
for i = 0 to n - 2
  for j = i + 1 to n - 1
    if U[i] <= U[j]
      Temp[j]++
    else
      Temp[i]++
//3. Now Temp has the correct "index" order so create an array S and place the elements of U into it using Temp
for i = 0 to n - 1
  S[Temp[i]] = U[i]
return S

Я проверил несколько исходных несортированных массивов, и он каждый раз корректно сортируется.Задача этого домашнего задания не состоит в том, чтобы отказаться от этого алгоритма и написать известный алгоритм сортировки.Скорее, я должен определить, возможно ли «просто» модифицировать вышеупомянутый алгоритм так, чтобы сложность времени была меньше, чем n ² .Ясно, что этот квадратик делает вложенные циклы, но я не вижу способа использовать Temp таким же образом без двух вложенных циклов.