2

We were tasked to sort a queue in O(n log n) using basic functions such as enqueue, dequeue, peek, empty only. Additionally, we may use another queue to help us. No other data structures are allowed.

Having trouble coming up with a solution as I feel like this is possibly an modification of a divide-and-conquer problem but I am unable to come up with a solution using the 4 basic functions.

Is it possible to receive some hints to solve this problem?

Math.anony
  • 87
  • 1
  • 6
  • By enqueue and dequeue you mean basic push and pop? – nice_dev Sep 29 '21 at 16:21
  • Yup, enqueue == push and dequeue == pop – Math.anony Sep 29 '21 at 16:26
  • More precisely, enqueuing will happen from the bottom and dequeuing from the top? – nice_dev Sep 29 '21 at 16:30
  • 1
    Yup. For example a queue, q, with elements {1, 2, 3, 4}. q.push(5), elements = {1, 2, 3, 4 ,5} q.pop(), elements = {2, 3, 4, 5} – Math.anony Sep 29 '21 at 16:34
  • 1
    You can do a merge sort using queues. – nice_dev Sep 29 '21 at 16:37
  • When you say 4 basic functions, are we allowed only those 4? I presume you may need to clarify that once again with the guy who gave this question. – nice_dev Sep 29 '21 at 16:38
  • Since a queue is implementable as a singly linked list that keeps a reference to its tail, [this post](https://stackoverflow.com/questions/7685/merge-sort-a-linked-list) may be able to help you out, or one of the other 'Merge sort a linked list' questions in other languages. – kcsquared Sep 29 '21 at 16:43
  • 1
    Are any variables allowed other than the 2 queues? – trincot Sep 29 '21 at 17:16
  • Are you limiting things to one additional queue, or would two be allowed? If the queues are linked lists, then it's only a constant amount of additional storage. – pjs Sep 30 '21 at 22:24

1 Answers1

10

Given queue A full and queue B empty, if A consists of sorted groups of w elements, then you can merge them in pairs to produce sorted groups of 2w elements as follows:

  1. While(A.length - B.length > w), pull w elements out of A and put them in B. A and B will then both consist of sorted groups of w elements, plus some left over.

  2. repeatedly pull w elements from both A and B, merging them onto the back of A to create sorted groups of 2w elements. Stop when all the elements have been processed (be careful not to pull elements from A that you already processed. You'll need to remember its original size). A will then consist of of sorted 2w groups, and B will be empty again.

Repeat the above procedure with w=1 (groups of 1 are always sorted), then w=2, w=4 ... w=2n, etc. until the whole queue is sorted.

Matt Timmermans
  • 53,709
  • 3
  • 46
  • 87