Algorithm - Quick Sort
 worst-case time complexity but an average speed of O(N logN).
Quick Sort works by selecting one pivot number (usually the middle number) as a reference point, dividing the array into left and right sections called partitions, then moving numbers smaller than the pivot to the left partition and larger numbers to the right partition.
Then a new pivot is selected in each partition and the same process repeats recursively, continuing the sort.
This approach is very similar to binary search.
Because of this, the actual time complexity is also similar to O(N LogN).
However, if you always pick the smallest number as the pivot, you end up comparing all other numbers and placing them on the right, resulting in O(N^2).
To minimize such cases, there are methods that select the pivot randomly.
Below is a Quick Sort implementation in Python:
def QuickSort(mylist):
# If the input list size is less than 1, return the input as-is and exit the function.
if(len(mylist) <= 1):
return mylist
# Set the middle number of the input list as the pivot number
pivot = len(mylist) // 2
# Create left and right partitions as arrays, and declare the middle value as an array too to concatenate with other arrays using the + operator.
leftList, rightList, equalList = [],[],[]
# Start Quick Sort
for num in mylist:
if(num < mylist[pivot]):
leftList.append(num)
elif(num > mylist[pivot]):
rightList.append(num)
else:
equalList.append(num)
return QuickSort(leftList) + equalList + QuickSort(rightList)
By the way, most programming languages provide a built-in sort() function, and most of them use Quick Sort or a more optimized version of it under the hood.