Author: Stan Eisenstat
Subject: Re: [Cs223] None
Date: Wednesday, 04 Mar 2020, 22:05:24

    > Message Posted By: Cocktail Sort Explanation
    >
    > As a follow-up to the previously asked question, can the reasoning for why
    > cocktail sort runs in that time/uses that many pushes be explained as
    > well?

First you pour N elements from Stack A to Stack B,
except for the largest which is returned to Stack A.
Total #pushes = N.

Then you pour N-1 elements from Stack B to Stack A,
except for the smallest which is returned to Stack B.
Total #pushes = N-1.

Then you pour N-2 elements from Stack A to Stack B,
except for the largest which is returned to Stack A.
Total #pushes = N-2.

Then you pour N-3 elements from Stack B to Stack A,
except for the smallest which is returned to Stack B.
Total #pushes = N-3.

...

N(N-1)/2 pushes later, the smallest N/2 elements are in
Stack B in decreasing order from the top, and tne half
the elements are in Stack A in increasing order from the
top.  Now pour the N/2 elements in Stack B to Stack A.
Total #pushes = N/2.

Overall total: N/2 + N(N-1)/2.

--Stan-