0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Welcome to MSE! Did you have any progress on this problem? And did you try working out the worst case complexity too? $\endgroup$ – Minus One-Twelfth Mar 1 at 14:49
  • $\begingroup$ This is very like insertion sort, of course. You might want to try solving the problem for insertion sort first, as it may be a bit simpler, and it will probably give you a good idea how to solve this problem. $\endgroup$ – saulspatz Mar 1 at 14:53
  • $\begingroup$ Quick answers ! I edited my post to answer your question @MinusOne-Twelfth ! $\endgroup$ – DonutsSauvage Mar 1 at 15:11
  • $\begingroup$ @saulspatz what I'm assuming I'm struggling with is not really the time complexity of any sorting algorithm, but rather determining how many times it will be called on average (but then again, you surely had a good reason to leave a comment like you did, could you elaborate a bit more on it please ?) $\endgroup$ – DonutsSauvage Mar 1 at 15:11
  • $\begingroup$ Actually, it was for that very reason. The important thing is figuring out the number of times the sort routine is called. I was just suggesting that using a simpler sorting algorithm will allow you to concentrate on the important part first. $\endgroup$ – saulspatz Mar 1 at 15:20
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hmm... I've edited the post with how far I've gotten thanks to your advices. But I must say your question is puzzling. Assuming the sorting routine starts at $aj$ then it means the first $j-1$ elements where higher than $a1$ thus $aj$ is the smallest of the first $j$ elements. Or did I get it wrong ? $\endgroup$ – DonutsSauvage Mar 2 at 13:10
  • $\begingroup$ @DonutsSauvage I think I must have misread the algorithm. As I read it again, I don't see how it assures that the array gets sorted, which is not how I understood it before. Sorry if I've led you astray. $\endgroup$ – saulspatz Mar 2 at 13:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.