Expected running time to sort an array N using K mergesort on sub-arrays of N

Question

I'm reaching out to this community today regarding a problem I found in a book and that I deem to be really interesting but that I have troubles solving.

Assume that all the elements in the input array $A = <a1,...,an>$ are distinct and in random order. We want to sort this array using the algorithm below:

1. temp <-- a1
2. for j=2 to n:
   • if aj < temp:
   • • temp <-- aj
   • • sort $<a1,...,aj>$ using mergesort

Assuming the time complexity of mergesort is $l.log(l)$ when sorting an arrat of size $l$, compute the expected running time of this algorithm.

So here it is. Sorry for the formating but this is the best result I could produce.
So far I've tried applying reasonings similar to the ones on randomized quicksort but to no avail, since in this case what I think concerns us is the actual number of time this algorithm is going to be running mergesort. Assuming the worst-case scenario (the array would be sorted from highest-to-lowest number) then the algorithm would execute mergesort at every step on an array whose size would grow by one every iteration. IMO this is not what is asked since this scenario is unlikely, and that's why I have troubles answering. I think we are looking for the average running time and I can't find it.
Also, since it kinds of kills all the fun if people give me the answer, I would really appreciate it if the persons answering my question could rather hint me towards the solution.

Edit 1. I'm assuming the worst-case to be $$(n-1)\left(\sum_{k=2}^n k.log(k)\right)$$

Edit 2. Following advices given to me, I've looked into searching how many time the mergesort would be called considering an 'average luck' (neither worst nor best case, something in-between). We know the algorithm executes $for$ $j=2$ $to$ $n$ meaning it executes $(n-1)$ times in total $(1)$.
Now since every element in the array is distinct, we only have 2 cases:
1. $aj$ > temp
2. $aj$ < temp
This could be simplified as a $\frac{1}{2}$ probability of $aj$ < temp $(2)$.
Adding $(1)$ and $(2)$ together we get that the expected running time for this algorithm is $$\left(\frac{n-1}{2}\right).(something)$$ with $something$ being the running time of mergesort $l.log(l)$ everytime it's called. Now in order to be able to actually compute this I thought of storing in a separate array B every number $aj$ for which the algorithm executes the sorting routine. Which in the end would give us the expression: $$\left(\frac{n-1}{2}\right).\left(\sum_{i=0}^k B[i]\right)$$ assuming $B.size = k$. Now (assuming the formula is correct) this would probably work but it's more of a trick than an actual pure mathematical solution.

Answer 1

HINT: When you look at $a_j,$ the first $j-1$ elements have already been sorted, and the important question is where does $a_j$ belong in a sorted list of the first $j$ elements? Is it the largest, the second largest, ..., the smallest? Since the elements were randomly arranged at the beginning, all these possibilities are equiprobable.