I need to find a tight bound on the number of comparisons in a d-ary heapsort, in terms of d and n (the length of the array we want to sort).Since inserting n items to a heap takes O(n) , and each delete-min takes O(d log n/ log d), I was thinking the bound is O(n d log n / log d). Am I right? If so, how do I prove that it is indeed a tight bound?Thanks.
d-ary heapsort analysis
data structures;runtime analysis;sorting;heaps