Trying to make a sorted array of the indexes of another array in an extremely limited version of "python"

Question

I'm trying to make a sorting function that will make an array of the indexes of the "input array."

Eg. Array(19,21,15,50,14) would return Array(4,2,0,1,3)

That may sound easy, but the version of "python" I am using is very limited. (Don't ask which or why it's in quotes, that's not the point.) Here are the limitations:

• Cannot pass variables through functions (return, and stuff like def func(var2, var1)), but I can use them to change the values of global variables
• Cannot use embedded arrays
• Cannot use any "pre-built" python functions like sort() or something
• Cannot change the values of 2 variables in the same line, e.g. var1,var2 = var2,var1

I'm looking for a way to do this with the lowest time complexity. I feel like I know how to do this with a bubble sort or insertion sort, but the array I'll need to sort is 41 items long...

I've tried to write mergesorts and quicksorts since they have low time complexity but I have no idea how to do them without carrying variables between functions.

If you do come up with an algorithm please write it in python so that I can translate it into my very cool version of python.

Answer 1

Based on the question's premises, the array to be sorted is global, like array[].

Declare a global array of indexes: index[]. Sort the indexes according the the values in the global array. Compare would use something like (array[index[i]] <= array[index[j]]). If it is only 41 values, insertion sort should be fast enough, as it is common for library sorts to use insertion sort for groups of 64 values or less due to being cache friendly and also stable (order of equal elements preserved).

You could then reorder index[] and array[] to sort index[] and array[] in O(n) time, if that was to be done later. This is mostly used to sort several arrays according to one of them: sort array1[], array2[], array[3], ..., according to values in array1[].

C++ could do this generically (non-global array) using a template with a lambda compare.