NOTE: Not particularly a C++ programming question, rather than a general programming question. Code was done in C++ though, so I chose this sub-forum.
As part of a data structures project, we're asked to implement three sorting algorithms, Mergesort, Heapsort and Counting Sort. We're asked to give increasingly large inputs (I've used dynamically allocated integer arrays with up to 100 million items) and fill the input tables with:
a) Random-number generator (rand() didn't cut the mustard in such big tables as it only allows for a range of 32768, and the ways to get a proper random seed deemed frustrating, so I used an implementation of Mersenne Twister.)
b) Worst-case inputs
The first part is easy to implement, but the second part requires some good guessing, as there's no proper bibliography for sorting algorithms' worst-case inputs. The only thing you'll find is things such as "Heapsort [...] has the advantage of a worst-case Θ(n log n) runtime."
Worst-case inputs for algorithms like Bubble-sort could be easy to guess, a descendingly ordered input, for example. Counting sort requires more time as the range of numbers increases. However, Mergesort and Heapsort use more advanced methods of sorting, and I'm quite stumbled as to how to arrange the input to get a worst-case one.
I'm not asking you to solve my homework or give me the full answer, I'm just asking if anyone has an idea and can point me to the right direction.
I'd be glad to get an answer anytime, even after the deadline is due.
