If the input is in descending order then the loop will execute n^2 times.
For n = 16 , loop will execute 256 times
Here’s small code depicting this,
Q = [16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1] // considering index 0 as head of Q
S =[]
i=0
while(Q.length){
if ( !S.length || S[S.length-1]<=Q[0] ) {
x = Q.splice(0,1);
S.push(x[0]);
}
else{
x = S.splice(S.length-1,1);
Q.push(x[0]);
}
i++;
console.log(i +"|" + Q+ "|"+S) //will give iteration no. And elements in Q & S
}
P.S. The code is written in JS, If u wanna run it just copy the code , Right click on the web browser(CHROME) any page select Inspect And in the console tab just paste the code And hit enter