---

Answer:

The most efficient sorting algorithms is Quicksort and mostly used sorting technique as well.

It is an algorithm of Divide and Conquer type. The details are as follows:

Divide

Rearrange the elements and split arrays into two sub-arrays and an element in between search that each element in left sub array is less than or equal to the average element and each element in the right sub- array is larger than the middle element.

Conquer

Recursively, sort two sub arrays.

Combine

Combine the already sorted array.

QUICKSORT (array A, int a, int b)   
 1 if (b > a)   
 2 then   
 3 i ← a random index from [a,b]   
 4 swap A [i] with A[a]   
 5 o ← PARTITION (A, a, b)   
 6 QUICKSORT (A, a, o - 1)  
 7 QUICKSORT (A, o + 1, b)  

PARTITION (array A, int a, int b)   
 1 x ← A[a]   
 2 o ← a   
 3 for p ← a + 1 to b  
 4 do if (A[p] < x)   
 5 then o ← o + 1   
 6 swap A[o] with A[p]  
 7 swap A[a] with A[o]   
 8 return o 

Explaination

The first thing to do is to select a pivot number, this number will separate the data, on its left are the numbers smaller than it and the greater numbers on the right.

With this, we got the whole sequence partitioned.

After partitioning the data, we can assure that the partitions are oriented, we know that we have bigger values on the right and smaller values on the left. The quicksort uses this divide and conquer algorithm with recursion.

Therefore, now that we have the data divided we use recursion to call the same method and pass the left half of the data and after the right half to keep separating and ordinating the data.

At the end of the execution, we will have the data all sorted.

Time Complexity

Best Case Complexity

The best-case occurs when the pivot element is the middle element or near to the middle element. The best-case time complexity of quicksort is O(n*logn).

Average Case Complexity

It occurs when the array elements are in jumbled order that is not properly ascending and not properly descending. The average case time complexity of quicksort is O(n*logn).

Worst Case Complexity

The worst case occurs when the pivot element is either greatest or smallest element. Suppose, if the pivot element is always the last element of the array, the worst case would occur when the given array is sorted already in ascending or descending order. The worst-case time complexity of quicksort is O(n²).

👈       👉