Complexity: O(n)

Algorithm

int *left = 0; 
int right = LAST_INDEX; 

while (left <= right) {
	while (array[left] <= pivot) {
		left++; 
	}
	// at this step we have found element array[i] which is > pivot, but in left half
	while (array[right] > pivot) {
		right--; 
	}
	// at this step we have found element array[i] which is <= pivot, but in right half

	swap(array[left], array[right]); 

	left++; 
	right--; 
}*

In video format:

https://www.youtube.com/watch?v=NuQYFXmLUrM&t=22s