1: function G-SORT(A, n) . takes as input an array of n numbers, A[1..n]

2: G-sort-recurse(A, 1, n)

3: end function

4: function G-SORT-RECURSE(A, `, u)

5: if u ` 0 then

6: return . //1 or fewer elements already sorted

7: else if u ` = 1 then // 2 elements

8: if A[u] < A[`] then . swap values

9: temp A[u]

10: A[u] A[`]

11: A[`] temp

12: end if

13: else . 3 or more elements

14: size u ` + 1

15: twothirds d(2 size)/3e

16: G-sort-recurse(A, `, ` + twothirds 1)

17: G-sort-recurse(A, u twothirds + 1, u)

18: G-sort-recurse(A, `, ` + twothirds 1)

19: end if

20: end function

, Derive a recurrence for the algorithms running time and , obtain a good asymptotic upper bound (big-O) for your recurrence