[HW1] Confusion on the HW speed and baseline speed

[BaichenRong]

I am very confused right now. I have tried 3 days sitting right behind my computer testing about the speed to check if it can surpass the baseline. Ideally, surpassing the baseline should not be that difficult and Introsort is just consistent but not superiorly fast. My logic is to first use a method to differentiate ascending, descending, mostly ascending, mostly descending, and totally random. Then, I apply different kinds of sorting algorithms that Dr. Choi taught us in the class to match each type. However, I tried so many different combinations but I failed to surpass the baseline. Could you please tell me if my logic is correct? Thank you!

[caroltang0331]

I kind of tried the same thing and couldn't get it faster either, so maybe its the logic itself. so confused

[BaichenRong]

In HW, it said we cannot merge the row at first. Thus, the only thing we can do is to sort each row based on its property. Unfortunately, when we combine them together, we need another sort! Because even though each row is in the right place, the final combined 1d array is still not in ascending order.

[marvinquiet]

Right, you can apply the same idea as a merge sort for sorting different rows. But the overall performance should be faster because when it has the property, the best algorithm can have O(n) to sort

[BaichenRong]

Thank you for your reply! I will think about it further!