ANONYMOUS wrote:
> Hi Gozz, thank your clarification. Below I'd like to try my hand at the open-ended questions you have provided.
> 1. Do you believe heap sort is a distribution sort? What is your argument to support your position? Can you formulate a counterargument?
> - From a standpoint of heap sort being distribution sort, it could be stated that splitting the list into heaps can be considered as blocks.
Heap sort only uses a single heap, though. Heaps are typically implemented as binary trees with the heap property, so maybe you are talking about the subtrees of the heap?
Recall that one of the defining parts of a distribution sort is that there should be no inversions between "blocks". Do the subtrees of the heap have this property? Does the heap property imply anything about inversions?
> However I believe that heap sort is mainly a comparison sort as it only provides 1 bit of information (i.e. parent is larger/smaller depending on if the heap is max/min heap) and comparison is needed for its main function (heapify) to maintain the heap property.
As demonstrated by quicksort, being a comparison sort does not mean something cannot be interpreted as a distribution sort. So the fact that heap sort is a comparison sort does not mean it is not a distribution sort.
> 2. Could you adapt merge sort to use more information than just comparison? If so, how does your resulting algorithm relate to others we have covered in lectures (what is it similar to, etc.)?
> - One adaption I could think of is instead of dividing the list until it can be trivially sorted, we divide until a certain list size is achieved (e.g. List size of 10) and use counting sort which can provide the information of cumulative count. This also brings the advantage of reduced overhead as we do less recursive calls.
What you have proposed is a hybrid sort which switches from merge sort to counting sort at a particular list size. Compare this concept to introsort, which as described in the lectures switches from quicksort to heap sort at a particular depth if quicksort hasn't already hit a base case.
I would argue that merge sort isn't using the extra information here, you are just switching out to one that does, but trying to construct a hybrid sort is a reasonable approach.
To be a variant of merge sort, I would argue it still has to split the list without regard for the elements, and the reordering is done as part of merging. Given that merging is already linear time, even using extra information couldn't get us any wins there... At least for two lists. Perhaps there is a way to efficiently merge more than two lists by using more information than just comparison?
> Please let me know if I have any error in my logic/understanding. Thank you for your time and advice
I want to be clear that I mean it when I say these are open-ended. There is not a "correct" answer I am looking for. They are questions to reason about and see if you can come up with interesting ideas. It is possible (and perhaps even likely) that the answer to both is "no, that doesn't make sense", but the point is to have an explanation for why it doesn't make sense, or why it does (if it does).
I hope you are enjoying exploring a more open-ended problem.
Cheers,
Gozz
