JAVA

Describe an efficient integer sorting algorithm using a linked list based queue. The initial n values and a marker are already in the given queue and you have another n write-only spaces and O(1) extra space. The marker is always the last ele- ment of the queue. At last, the n write-only spaces must have the values in sorted order without the marker.

For example, the initial queue is [2 1 3 4 #] where # is the marker.