# Sorting Algorithms

Sorting is the process of arranging data in a particular order (usually ascending or descending). Efficient sorting is critical for optimizing the performance of other algorithms (like search) that require sorted input data.

## 1. Merge Sort

Merge Sort is a "Divide and Conquer" algorithm. It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves.

*   **Time Complexity:** $O(n \log n)$ in all cases (Best, Average, Worst).
*   **Space Complexity:** $O(n)$ (requires auxiliary space for merging).
*   **Stability:** Stable (preserves the relative order of equal elements).

### How it Works
1.  **Divide:** Find the middle point to divide the array into two halves.
2.  **Conquer:** Recursively call `mergeSort` for the first half and the second half.
3.  **Combine:** Merge the two halves sorted in step 2.

### Implementation (Python)

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

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

    return merge(merge_sort(left_half), merge_sort(right_half))

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

    # Compare elements from both lists and add the smaller one
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_arr.append(left[i])
            i += 1
        else:
            sorted_arr.append(right[j])
            j += 1

    # Add remaining elements
    sorted_arr.extend(left[i:])
    sorted_arr.extend(right[j:])
    return sorted_arr
```

## 2. Quick Sort

Quick Sort is also a "Divide and Conquer" algorithm. It picks an element as a **pivot** and partitions the given array around the picked pivot.

*   **Time Complexity:** $O(n \log n)$ on average, but $O(n^2)$ in the worst case (rare, happens if the pivot is always the smallest/largest element).
*   **Space Complexity:** $O(\log n)$ (stack space for recursion).
*   **Stability:** Unstable (relative order of equal elements might change).

### How it Works
1.  **Pick Pivot:** Choose an element (e.g., the last element).
2.  **Partition:** Reorder the array so that all elements with values less than the pivot come before the pivot, and all elements with values greater than the pivot come after it.
3.  **Recursion:** Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.

### Implementation (Python)

```python
def quick_sort(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 quick_sort(left) + middle + quick_sort(right)
```

## 3. Comparison

| Algorithm | Time (Avg) | Time (Worst) | Space | Stable? | Best For |
| :--- | :--- | :--- | :--- | :--- | :--- |
| **Merge Sort** | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ | Yes | Linked Lists, large datasets where stability matters. |
| **Quick Sort** | $O(n \log n)$ | $O(n^2)$ | $O(\log n)$ | No | Arrays, general purpose in-memory sorting. |
| **Bubble Sort** | $O(n^2)$ | $O(n^2)$ | $O(1)$ | Yes | Small datasets, educational purposes. |

[[programming/algorithms]]
[[programming/recursion]]
[[programming/arrays-and-lists]]