Hello, curious learner! You've made it more than halfway through our learning path, and today, we will embark on a journey through the Quick Sort world. Picture yourself organizing various items — like toys or books — by size or color. That's what Quick Sort does with spectacular speed. Are you ready to explore further? Fantastic! Let's get started.

Quick Sort is a clever little algorithm invented by a British computer scientist named Tony Hoare in 1959. It uses a strategy called divide-and-conquer to put elements in order. Quick Sort takes an array, selects a particular "pivot" element, and then places everything smaller than the pivot on one side and everything larger on the other.

Quick Sort has a three-step process:

1. Pick a random "pivot" element from the array.
2. Move all elements smaller than the pivot to one side and bigger ones to the other. This operation effectively divides the array into two parts, guaranteeing that all the elements will be kept within their part until the end of the sorting process.
3. Repeat steps 1 and 2 for each part until there are no more unsorted elements.

For example, let's say we have nine marbles with numbers: [3, 9, 4, 7, 5, 1, 6, 2, 8].

We choose a marble, called the pivot, to help us sort the others. For this example, let's pick 7 as the pivot.

After the first round of sorting, we rearrange the marbles so that all marbles smaller than 7 are on the left, and all marbles larger than 7 are on the right.

The result would look like this: [3, 4, 5, 1, 6, 2, 7, 9, 8].

At first, this might seem like a small change, but notice that the pivot (7) is now in its correct position in the sorted array! The important part is that now we can treat the left side [3, 4, 5, 1, 6, 2] and the right side [9, 8] as separate sections. These sections will never change or mix again, because the pivot is already in its place.

The Quick Sort algorithm requires two main functions to implement: Partition and QuickSort. Let's delve into each of them.

func Partition(arr []int, start, end int) int {
    pivot := arr[end] // choosing the last element as pivot
    i := start - 1  // marking the index of the smaller element

    for j := start; j < end; j++ {
        // checking if the current element is smaller than the pivot
        if arr[j] <= pivot {
            i++
            // swap arr[i] and arr[j]
            arr[i], arr[j] = arr[j], arr[i]
        }
    }
    // Swap arr[i+1] and arr[end] (or pivot)
    arr[i+1], arr[end] = arr[end], arr[i+1]

    return i + 1 // return the partition point
}

The Partition function is responsible for splitting the array into elements lesser and greater than a chosen pivot element. Here, the pivot is the last element of the section defined by start and end. The index i tracks the position of the last element less than or equal to the pivot. As the function iterates through the array using index j, it compares each element to the pivot. If an element is smaller or equal, i is incremented, and the element at arr[j] is swapped with arr[i]. Finally, the pivot is swapped into its rightful position at i+1, and this index is returned, providing a point to divide the array for further sorting.

Next, we will cover the QuickSort function:

func QuickSort(arr []int, start, end int) {
    if start < end {
        pivotIndex := Partition(arr, start, end) // find the pivot index
        QuickSort(arr, start, pivotIndex - 1) // sort left part
        QuickSort(arr, pivotIndex + 1, end)   // sort right part
    }
}

The QuickSort function is the main component that orchestrates the sorting process. It takes an array arr with two indices, start and end, marking the section of the array to work on. When start is less than end, the section is divided with the Partition function, determining the pivotIndex. After partitioning, QuickSort is recursively applied to the left part (start to pivotIndex - 1) and right part (pivotIndex + 1 to end). This recursive approach continues until all elements are sorted.