What is the difference between quicksort and merge sort?

QuickSort and Merge Sort are comparison algorithms that use the "divide and conquer" strategy but differ in their approaches to dividing and merging data.

Main differences:

1. Approach to division:

   • QuickSort: Selects a pivot element and partitions the array into two parts: elements less than the pivot and elements greater than the pivot. Then recursively sorts these parts.
   • Merge Sort: Divides the array in half, recursively sorts each half, and then merges the sorted halves.

2. Approach to merging:

   • QuickSort: Merging is trivial since elements are already positioned relative to the pivot.
   • Merge Sort: Merges sorted subarrays by comparing elements to build a new sorted array.

3. Stability:

   • QuickSort: Not a stable sort (may change the relative order of equal elements).
   • Merge Sort: Is a stable sort.

4. Memory usage:

   • QuickSort: Usually an in-place sort but requires a recursive stack. Worst case O(log n) for the stack, O(n) in case of poor pivot choice.
   • Merge Sort: Usually requires additional O(n) memory for the temporary array during merging.

5. Performance:

   Case	QuickSort	Merge Sort
   Average	O(n log n)	O(n log n)
   Worst	O(n^2)	O(n log n)
   Best	O(n log n)	O(n log n)

6. Implementation:

   • QuickSort: Implementation can vary depending on the pivot choice and partition method.
   • Merge Sort: More straightforward implementation.

Example pseudocode:

# QuickSort
def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2] # Choosing a pivot
    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)

# Merge Sort
def mergesort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = mergesort(arr[:mid]) # Recursively sort the left half
    right = mergesort(arr[mid:]) # Recursively sort the right half
    return merge(left, right) # Merge sorted halves

def merge(left, right):
    result = []
    i, j = 0, 0
    while i < len(left) and j < len(right): # Merging
        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