Write a program/algorithm of Quick Sort Method and analyze it with example. Also explain best case, worst case and average case time complexity of it

Sure, here is a simple implementation of Quick Sort in Python:

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

print(quicksort([3,6,8,10,1,2,1]))

This program works by choosing a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted.

Let's analyze it with an example:

Consider the array [3,6,8,10,1,2,1]. The pivot is 8. The elements less than 8 are [3,6,1,2,1] and the elements greater than 8 are [10]. These sub-arrays are then sorted using the same quicksort method.

Time complexity analysis:

• Best case: The best case occurs when the partition process always picks the middle element as pivot. The time complexity in this case is O(n log n).

• Worst case: The worst case occurs when the partition process always picks greatest or smallest element as pivot. If we consider a sorted array as input, then the pivot is either the first or the last element. The time complexity in this case is O(n^2).

• Average case: Even in average case, the time complexity is O(n log n), but the hidden constant factors are higher compared to other sorting algorithms like Merge Sort.

Space complexity of Quick Sort is O(log n) in best case and O(n) in worst case.