Compare Merge Sort with Factorial and Randomized Inefficient Sorts

Problem Statement

In this technical evaluation, you are tasked with implementing an Adaptive Merge Sort and analyzing its time complexity guarantees in contrast with factorial-time deterministic sorts and randomized shuffle sorts.

Part 1: Implementation

Implement adaptive_merge_sort(arr: list[int]) -> tuple[list[int], int]:

1. Use a divide-and-conquer approach to sort arr out-of-place (or into a new list).
2. Incorporate an adaptive check during the merge phase: if the largest element of the left half is less than or equal to the smallest element of the right half, skip the full element-by-element merge and concatenate the halves directly.
3. Count and return the exact total number of element-to-element comparisons performed.

Part 2: Complexity & Paradigm Comparison

Prepare to rigorously explain and contrast the theoretical behavior of:

1. Merge Sort (Standard vs Adaptive): Explain why standard merge sort is strictly O(n log n) in best, average, and worst cases, and how the adaptive check achieves O(n) best-case without degrading worst-case bounds.
2. Permutation Sort (Deterministic Factorial): Systematically enumerating all n! permutations until a sorted one is found (O(n * n!) worst case).
3. Randomized Shuffle Sort (Bogo Sort): Repeatedly applying a uniform random permutation until sorted. Distinguish between Las Vegas randomized algorithms, expected runtime (O(n * n!)), and unbounded worst-case runtime (O(infinity)).

Function Signature

def adaptive_merge_sort(arr: list[int]) -> tuple[list[int], int]:
    """
    Sorts an input list using adaptive merge sort.
    Returns a tuple of (sorted_list, comparison_count).
    """
    pass

Examples

Example 1:

Input: arr = [1, 2, 3, 4]
Output: ([1, 2, 3, 4], 3)
Explanation: 
- Split into [1, 2] and [3, 4].
- [1, 2] splits into [1] and [2]; 1 comparison determines 1 <= 2.
- [3, 4] splits into [3] and [4]; 1 comparison determines 3 <= 4.
- Merging [1, 2] and [3, 4] checks if 2 <= 3 (1 comparison). Since true, full merge is bypassed.
Total comparisons = 3.

Example 2:

Input: arr = [4, 3, 2, 1]
Output: ([1, 2, 3, 4], 5)
Explanation:
- Split and sort left [4, 3] -> [3, 4] (1 comparison).
- Split and sort right [2, 1] -> [1, 2] (1 comparison).
- Adaptive check compares 4 <= 1 (False, 1 comparison).
- Standard merge proceeds between [3, 4] and [1, 2] taking 2 comparisons (1 vs 3, 2 vs 3).
Total comparisons = 5.

Constraints

• 0 <= len(arr) <= 10^5
• -10^9 <= arr[i] <= 10^9
• The comparison counter must only increment when two elements from arr are directly compared.