Comparison Count in Quick Sort vs Merge Sort

In this problem, you are given a list of n integers. Your task is to simulate two popular sorting algorithms: Quick Sort and Merge Sort. However, instead of fully sorting the array, you need to count the number of comparisons each algorithm makes when sorting the array.

More formally, let ( C_{QS} ) be the number of comparisons made by Quick Sort and ( C_{MS} ) be the number of comparisons made by Merge Sort. You should output:

• "Quick Sort" if ( C_{QS} < C_{MS} ),
• "Merge Sort" if ( C_{MS} < C_{QS} ),
• "Same" if ( C_{QS} = C_{MS} ).

Both algorithms are implemented recursively. In the Quick Sort simulation, choose the last element as the pivot. In the Merge Sort simulation, count one comparison for each comparison between elements during the merge process. Please note that the formulas and recurrences involved might help you understand the complexity of these algorithms, but your task is only to compare the total number of comparisons for the two methods.

inputFormat

The first line of the input contains a single integer ( n ) (the number of elements). The second line contains ( n ) space-separated integers representing the array elements.

outputFormat

Output a single line containing one of the strings: "Quick Sort", "Merge Sort", or "Same", based on which algorithm finishes with fewer comparisons (or if they are equal).## sample

5
3 5 1 9 6

Merge Sort