Do you know the example B from AtCoder given as test problem to test their interface? You should sort an array interactively, asking which of 2 elements is bigger and swapping or doing whatever you want with this information. Constraints are 26 elements to be sorted

1) with <=1000 comparisons

2) with <=100 comparisons

and (3) — 5 elements to be sorted with 7 comparisons.

For each of 3 variants you get 100 points — AtCoder rules.

You can ask yourself how many comparisons are necessary. And why 100 and 1000. Maybe you have also heard about bubble sort and merge sort. The answers of ChatGPT o1-mini were long, so I just post my questions:

1) how many operations do I need to sort an array of size n with the merge sort?

2) But there are different cases, worst case and best case?

3) Can you break down the worst case for n=26, how many comparisons should be done in each step. The first step is 13 comparisons to get 13 sorted arrays with 2 elements each. And then? Assume that each merge needs maximum of comparisons, because the initial array is arranged in the worst thinkable way.

// here, it counted 115 comparisons — too much, because constraint is 100. So, I gave him an idea

4) we should adjust the scenario in a way that we merge the smallest array so early as possible, not at the end when we have one array of 24 and one of 2.

// here, it counted 88 comparisons in the worst case — constraint Ok!

5) what is the sum of 1 + 2 + ... + n ? // asking for bubble sort

// n * (n + 1) / 2

6) Is it also a number of operations needed to sort an array of n with the bubble sort?

// no, it is n * (n — 1) / 2

Here it is clear, why constraint 1000. It is for those who can't implement merge sort but can bubble sort, they get only this variant done. But if you can merge sort, you don't need bubble sort in this problem

7) how many comparisons do we need for n=5 in the worst case with merge sort?

// 8

hm, constraint is 7

8) Is there a way to sort an array of size 5 with 7 comparisons?

// yes, because ceil(log2(5!)) == 7

// you need a custom decision tree