Mark As Completed Discussion

How does this work in practical terms? Here's a gif of it being processed. Focus on how each "grouping" is grown as we iterate through the elements.

Step Seven

Here's another illustration that goes step by step. In this example, we start off with low and mid as 0, and high as (arr.length - 1), or 5 in this case. Really try to intuitively see the "growth" of each grouping.

Just as importantly, notice how the indices change over time, and try to see why they change.

Step Seven

So what exactly are we doing? We start by analyzing the element just above the middle pointer, which is 0 at first. If that element belongs to the top group (2), swap it with the element just below the top.

Otherwise, if it belongs in the bottom group (0), swap it with the element just above the bottom. Finally, if it is a mid-group (1), we'll leave it where it is but update the index. These moves are, in a sense, "wiggling" it to the right place via swaps.

Let us now analyze the complexity of this solution. Think about how many times we need to go through the array in the worst case. As we can see, we will only move mid to right and high to left. So they will go linearly and collide with each other, resulting in the finishing point of the algorithm. So the complexity of the whole algorithm is linear O(n). Here n is the length of the given array.

We are swapping the elements of the array in-place. And, we are not allocating any new memory except some variables. So the space complexity would be constant O(1).