Hector Hansen - 1 year ago 65
C Question

# Sort a big number list (100k) as quickly as possible using limited operations

I have two list : list A containing a set of random numbers and list B empty. I have to sort the list A.

I can make limited operations on these two lists like :

• move the first element of list A or B at the beginning of the list B or A

• swap the two first elements of list A or B like
`32 41 8 9`
become
`41 32 8 9`

• make the last element of list A or B become the first in this list (rotation) like
`32 41 8 9`
become
`9 32 41 8`

• make the first element of list A or B become the last one in this list (rotation) like
`32 41 8 9`
become
`41 8 9 32`

I have already set up an algorithm to sort the list A using the list B as the stack and the set of allowed operations, but it takes time when the list becomes large (more than 1000 elements) and is therefore not performing at all.

I have also try to set up a merge sort algorithm with this set of operations but with 10k of numbers it's take too many time (over 10 seconds).

Anyone have an idea of an efficient algorithm to perform this sort quickly ? I'm also using linked list and do my program in C to optimize the efficiency.