Sort the queue without using additional resources

Recently faced with such a task: "Merge two queues in such a way that the total queue was sorted." And the requirement for sorting is this: do not use any intermediate objects, except for one variable, no matter how slow the algorithm may be. The first attempts to create a queue sorting algorithm led to the question of how to get out of an infinite loop, but in the end I got the necessary algorithm, which will be discussed.

First, let's define the queue implementation, I will do it in Python using standard lists:

class EmptyQueueError(Exception): @staticmethod def message(): return 'queue is empty!' class FullQueueError(Exception): @staticmethod def message(): return 'queue is full!' class Queue: def __init__(self, max_size=None): self.__queue = [] self.__max_size = max_size def get_size(self): return len(self.__queue) def get_list(self): return self.__queue def push(self, item): if len(self.__queue) != self.__max_size or self.__max_size is None: self.__queue.append(item) else: raise FullQueueError def pop(self): if len(self.__queue): item = self.__queue[0] del self.__queue[0] return item else: raise EmptyQueueError def get_head(self): if len(self.__queue): return self.__queue[0] else: raise EmptyQueueError 

The set of methods is the most standard. The queue can be a fixed size, then a numeric parameter must be passed to the constructor, which determines the size, otherwise the queue will be infinite. The get_list () method is not safe because it returns a link to the internal list, and changing it from the outside is completely discouraged. But for debugging, it can be useful.

The exception classes EmptyQueueError and FullEmptyError respectively are responsible for controlling the void / fullness of the queue.
')
Now let's get down to the fun part - sorting the queue. Sorting occurs from the smallest element to the larger. We have the ability to use one variable to temporarily store an item from the queue. We also have a get_head () method that simply returns an element from the head of the queue. The basis of the sorting algorithm is that we place the next element in the temp variable using the pop () method. Further in the cycle we will compare the head of the queue with this temp , and if the head element is larger, then we place the temp at the end of the queue, and then assign the next element from the head ( pop () ) to it. If the head element is no more, then we put it in the tail, and we do not touch temp , that is, we rewind the queue for one element.

But the question is: when should the cycle be stopped?

When the algorithm finds the maximum, it is necessary to flush the queue completely to make sure that there is no greater value in the queue. This means that scrolling should be performed as many times as there are items in the queue. This requires a counter variable ( steps ). After scouring, you can safely push into the temp queue, and repeat the operation.

And in the case of finding a new maximum in the queue, reset the scroll counter to 0.

So we first assume steps = 0 , and if the next maximum is not detected, increase by 1.

But since after the execution of this cycle, the queue is unlikely to be sorted, it is necessary to repeat the operation as many times as there are elements in the queue without one, that is, the length_length is 1.

 def my_sorting(queue): for i in range(queue.get_size() - 1): temp = queue.pop() steps = 0 while steps < queue.get_size(): print(temp, queue.get_list()) if temp < queue.get_head(): queue.push(temp) temp = queue.pop() steps = 0 else: queue.push(queue.pop()) steps += 1 queue.push(temp) print(queue.get_list()) return queue 

Result: the queue is sorted without additional resources.