How does the quicksort algorithm differ from the merge sort method in terms of working principles and efficiency?

The algorithms of QuickSort and MergeSort differ in their working principles and efficiency as follows:

• Working principle:

  • QuickSort is a "divide and conquer" algorithm that selects a pivot element, then rearranges the elements so that those less than the pivot are on the left, and those greater are on the right, and recursively sorts the parts.
  • MergeSort also uses "divide and conquer," but divides the array in half, recursively sorts the halves, and then merges them into a sorted array.

• Complexity:

  • QuickSort on average operates in O(n log n), but in the worst case — O(n²), if the pivot is poorly chosen.
  • MergeSort guarantees a time of O(n log n) in all cases.

• Memory:

  • QuickSort usually sorts in place, requiring O(log n) additional memory for the call stack.
  • MergeSort requires additional memory O(n) for temporary arrays during merging.

• Application:

  • QuickSort is often faster in practice due to smaller constants and data locality.
  • MergeSort is stable (preserves the order of equal elements), which is important for some tasks.

Example of QuickSort 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)

Example of MergeSort:

def mergesort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = mergesort(arr[:mid])
    right = mergesort(arr[mid:])
    return merge(left, right)

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