How does Insertion Sort, Quick Sort, and Merge Sort work? Also what is the cost (Big Oh) of queue and stack operations?
<p>My apologies if this is long.</p>

<p><em><strong>Insertion Sort</em></strong></p>

<p>Lets start with Insertion Sort. I understand how Insertion Sort works but would like to clarify if I am understanding it correctly. Insertion Sort "brute forces" the array or whatever it is sorting. It starts from the very left position and the position after that. It sorts those two and keeps continuing until the whole array has been sorted. Here is the example in my head:</p>

<pre><code>[1] [5] [2] [58] [5] [27] [25]
 ^   ^
[1] [5] [2] [58] [5] [27] [25]
     ^   ^
[1] [2] [5] [58] [5] [27] [25]

[1] [2] [5] [58] [5] [27] [25]
         ^   ^

and so forth until it reaches

[1] [2] [5] [5] [25] [27] [58]
</code></pre>

<p><em><strong>Quick Sort:</em></strong></p>

<p>This is the one I understand the least and would like some clarification. The easiest way for me to understand this was watching this video: <a href="http://www.youtube.com/watch?v=ywWBy6J5gz8" rel="nofollow">http://www.youtube.com/watch?v=ywWBy6J5gz8</a>. From my understanding, a pivot point is chosen, most likely the median as it is the easiest and sorts. Choosing a bad pivot can lead to worse big oh behavior because of the number of inversions it has to make.</p>

<pre><code>[1] [5] [2] [58] [5] [27] [25]
             ^
            pivot

Sort the left side of the array

[1] [5] [2] [58]
 ^            ^

[1] [5] [2] [58]
^        ^

[1] [5] [2] [58]
 ^   ^

[1] [5] [2] [58]
     ^        ^

[1] [5] [2] [58]
     ^   ^

[1] [2] [5] [58]
         ^    ^

right side of the array

[5] [27] [25]
 ^        ^

[5] [27] [25]
 ^   ^

[5] [27] [25]
      ^   ^

[5] [25] [27]
</code></pre>

<p>merge the two arrays</p>

<p>Where does recursion take place? Sample code?</p>

<p>I believe this is how it works, PLEASE correct me if I am wrong.</p>

<p><em><strong>Merge Sort</em></strong></p>

<p>This one makes the most sense to me, split the array up until you you can't do it anymore. So array.length/2. Then this is where the confusing part sets in. You have the main array and you begin to sort, you start sorting from the very beginning through the array, two pieces at a time. Where do you determine how to iterate through the array, how do you determine your starting point and ending points when you are going through your array? Then you create a temp array and store it. This one is by far the hardest to explain so please forgive me. I looked at the wiki page for a better example for merge sort and it does a great job, but im just confused as to how it iterates through the main array and sorts it.</p>

<p>EDIT: <a href="http://en.wikipedia.org/wiki/Merge_sort" rel="nofollow">http://en.wikipedia.org/wiki/Merge_sort</a> this is the merge sort link to wiki.</p>

<p>If you notice how it splits into 1 element, then starts recombining, I understand how it arranges the first two elements. But what happens after that? How does it look in java code?</p>

<p><em><strong>Queue and Stack</em></strong>
After researching for a bit, I understand what these are. The one thing I haven't been able to look up is, what kind of Big Oh behavior do each of its techniques use?</p>

<p>for a stack this is what I THINK it is: Enqueue is constant, Dequeue is constant, and peek is constant</p>

<p>for a queue: Enqueue is constant, Dequeue is linear, and peek is linear.</p>

<p>if someone could clarify any of these things, or have any picture examples, I would greatly appreciate it,</p>

<p>Thank you.</p>
