2000, and the elements could be up to
arrof integers (not necessarily distinct), we split the array into some number of "chunks" (partitions), and individually sort each chunk. After concatenating them, the result equals the sorted array.
arrwill have length in range
arr[i]will be an integer in range