I am trying to understand Divide and Conquer algorithm, I learnt it through the Skyline problem and I was able to understand that quite well, however the below problem is giving me troubles. I was able to come up with a recursive algorithm for the same as shown below but I am unable to split it into smaller chunks and derive Divide and Conquer Algorithm, could someone please help me with the same?
You work at a school with $n$ students. Each student is initially in a group by themselves. The school would like to combine everyone into a single large group, but school policy says only two groups can be combined at a time. Every time two groups are combined, everyone from both groups must shake the hand of everyone else from both groups.
(Note that since each member of the two groups shakes hand with everyone in both groups being combined including those in their own group, one may end up shaking hands with the same student multiple times before all are combined)
Recursive Algorithm:
procedure $\mathrm{Group}(1, n)$
$ \quad $ if $n ==1$ then
$ \qquad $ return $P_1$
$ \quad $ else
$ \qquad $ return $\operatorname{Add}\bigl(\operatorname{Group}(1, n-1), P_n\bigr)$
where $P_1,\dots,P_n$ denotes $n$ initial groups of individual students and $\operatorname{Add}(a,b)$ denotes procedure which combines groups $a$ and $b$.
You probably want to focus on the general function $Group(a, b) $and then call it with $a=1,b=n$
Now you want to split the interval into halfs the middle happens at $(a+b) /2$ so you basically just add the two halfs $Group(a, b) = Add(Group(a, (a+b)/2,(a+b)/2+1,b)$
Now think about the base case of Group(a, b)?
It's when there's only one person in the group so $a=b$
So you add the rule if $a==b$ then$Group(a, b) = P_a$.