How can I sort a list in n log n with a storage of O(1) and non recursively?-CodePudding

I need to sort a list from smallest to greatest made on the mod of k. I am only able to use to do this in a purely iterative way, with nothing that is recursive. Basically the only thing I get is:

public static void sortMod(int [] a, int k)

How can I do this with only n log n runtime and O(1) space and without creating any new arrays?

CodePudding user response：

the .sort() method of the Array class can have a special argument which is the comparison function but I'm not sure it has the complexity you're looking for. Here is a list of algorithms with their complexities so you can try to implement one with you own comparison function.

CodePudding user response：

I don't think there is a sort algorithm with all of those characteristics:

Insertion sort, Selection sort, Bubblesort and its variants are all O(N^2)
Merge sort, Heapsort and Quicksort are all recursive
Shellsort is non-recursive, and O(NlogN) in the best case, but worse in the worst case. The worst-case analysis is complicated and depends on the "gap sequence" that you use; see https://en.wikipedia.org/wiki/Shellsort
Distribution sorts such as Counting sort, Bucket sort and Radix sort are non-recursive and O(N), but they require > O(1) auxiliary space.