Sort the Array

Time limit	Cycle limit	Code length	N
20 s	500,000	4,096 B	4096

Problem

You are given an integer array arr of length N = 4096. Write a function f(arr) that sorts the first N elements of arr in place, in non-decreasing order.

The only syntax allowed is reading/writing arr[i], integer arithmetic and bitwise operators, comparisons, and if / while. The array arr has extra scratch space after the first N cells.

Input

arr[0] through arr[N-1] are pre-filled with N unsigned 64-bit integers.

Output

When the function returns, arr[0] <= arr[1] <= ... <= arr[N-1] must hold.

Sample Input 1

arr = [5, 3, 1, 4, 2]   # when N = 5

Sample Output 1

arr = [1, 2, 3, 4, 5]

Submit

def f(arr): pass
Submit