Recursive sorting algorithm
Yes.

You can see that your sort function operates by recursing directly on itself, using a shorter-by-one version of its list parameter. This is stopped when the list is of length 0 or 1. (That code should be cleaned up.) So your sort recurses n-1 times, given n &gt;= 2.

Each time it recurses, sort calls push_up once. The push_up function linearly scans the list, which is of length 1, then 2, then ... n-1.

So in the worst case (input array is reverse-sorted) you have scans of total length \$ \sum 1 ... (n-1) \$, which makes your code \$ O(n^2) \$.