What sorting algorithms do you know?

Main sorting algorithms:

• Bubble Sort: A simple but inefficient algorithm that repeatedly passes through the list, swapping adjacent elements if they are in the wrong order.
• Selection Sort: Finds the smallest (or largest) element from the unsorted part of the list and places it at the beginning.
• Insertion Sort: Gradually builds a sorted list by inserting each new element into the correct position within the already sorted part.
• Merge Sort: A recursive algorithm that divides the list into sublists, sorts them, and then merges them back.
• Quick Sort: A "divide and conquer" algorithm that selects a pivot element and rearranges the elements so that those less than the pivot are on the left, and those greater are on the right. It then recursively applies to the sublists.
• Shell Sort: An improvement over insertion sort that compares elements separated by large gaps.
• Heap Sort: Uses a heap data structure for efficient sorting.

There are also less common but effective algorithms in certain cases, such as counting sort, radix sort, and bucket sort.

Average execution times of main algorithms:

Sorting Algorithm	Average Time Complexity
Bubble Sort	O(n²)
Selection Sort	O(n²)
Insertion Sort	O(n²)
Merge Sort	O(n log n)
Quick Sort	O(n log n)
Shell Sort	Depends on gap size
Heap Sort	O(n log n)

Example implementation of quicksort in Python:

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]  # Choose pivot element
    left = [x for x in arr if x < pivot]  # Elements less than pivot
    middle = [x for x in arr if x == pivot] # Elements equal to pivot
    right = [x for x in arr if x > pivot] # Elements greater than pivot
    return quicksort(left) + middle + quicksort(right) # Recursive sort and merge