Answer Happy

Suppose we have a new sorting algorithm that works as follows. Given array x, start at index i=0 and perform the following steps: 1. if i=0, increment i, return to step 1 2. if i==len (x), stop (the list is sorted) 3. if x < x[i-1], swap them, and decrement 1, return to step 1 4. if x 2 x[i-1], simply increment i, return to step 1 For example, if we were sorting [4, 3, 21, the steps would be: array i action [4, 3, 2] 1-0 i-0, so increment i [4, 3, 2] i=1 x[1] x [0], so swap and decrement i i-0, increment i [3, 4, 21 1-0 1-1 [3, 4, 2] [3, 4, 2] x[1] x [0], so simply increment i 1-2 [3, 2, 41 1-1 x[2] < x[1], so swap and decrement i x[1] < x[0], so swap and decrement i i-0, increment i 1=0 i-1 [2, 3, 4] [2, 3, 4] [2, 3, 4) [2, 3, 4] i=2 i=3 x[1]> x[0], so simply increment i x [2]> x[1], so simply increment i list is sorted! For an array of length n, what is the approximate average complexity of this sort algorithm? In other words, what is the order (big-O notation) that best describes the typical number of swaps, as a function of n, expected in this algorithm. Show your work and/or thoroughly explain your answer. Lucky guesses will be marked zero.