Part 1: In this report a new data strucutre named M-heaps is proposed. This data structure is a modification of the well known binary heap data structure. The new structure supports insertion in constant time and deletion in O(log n) time. Finally a generalization of the data structure to d-ary M-heaps is presented. This structure has similar time-bounds for insertion and deletion.
Part 2: In this report we present two schemes to reduce disorder of given elements and thus improve the performance of adaptive merge sorting. Adaptive sorting algorithms utilize the presortedness present in a given sequence. In the first scheme, amount of presortedness present in a sequence is probabilistically increased by using a swapping technique that requires little computation. In the second scheme alternate ascending and descending sequences present in the input are merged to decrease the disorder. In both the cases the analysis depends on a beautiful result about the average behaviour of permutaions which is stated and proved in the paper.
Report: Part 1 (PS-gzipped: 111K)
Report: Part 2 (PS-gzipped: 57K)