What is the difference between quicksort and merge sort?

The differences lie in the approach, implementation, and performance in various scenarios:

1. Approach:

   • Quicksort is a "divide and conquer" algorithm that works by selecting a "pivot" element and partitioning other elements into two subarrays depending on whether they are less than or greater than the pivot. The subarrays are then sorted recursively.
   • Merge Sort is also a "divide and conquer" algorithm that divides the list in half, recursively sorts the two halves, and then merges the sorted halves.

2. Stability:

   • Quicksort is not stable (the order of equal elements may change).
   • Merge sort is stable.

3. In-place execution:

   • Quicksort is usually performed "in-place," requiring minimal additional space (except for the stack space for recursive calls).
   • Merge sort requires additional space for temporary arrays during merging (O(n)).

4. Performance:

   • Average and best-case complexity: O(n log n) for both.
   • Worst-case complexity:
     • Quicksort: O(n^2) (e.g., with already sorted or reverse-sorted input array and poor pivot choice).
     • Merge sort: O(n log n) (always).
   • Impact on performance: On average, quicksort is faster than merge sort due to better practical performance and a smaller constant factor in O(n log n), although its worst case is much worse.

Characteristic	Quicksort	Merge Sort
Approach	Partitioning	Merging
Stability	No	Yes
In-place	Yes	Requires extra space
Worst-case complexity O	n^2	n log n

Example of quicksort:

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)

# usage example
# my_list = [3, 6, 8, 10, 1, 2, 1]
# sorted_list = quicksort(my_list)
# print(sorted_list)

Example of merge sort:

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]

    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)

    return merge(left_half, right_half)

def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result

# usage example
# my_list = [3, 6, 8, 10, 1, 2, 1]
# sorted_list = merge_sort(my_list)
# print(sorted_list)