CSCAN Sorting with Time Complexity O(log n)

Maintain two queues which will be sorted in ascending order using Red Black Trees. When a disk request arrives and if the block number it refers to is greater than the block number of the current request being served add (merge) it to the first sorted queue or else add (merge) it to the second sorted queue. Keep on servicing the requests from the first request queue until it is empty after which switch over to the second queue and now reverse the roles of the two queues. Simple and Sweet.