2.3.3. Sorting Algorithms

Sorting Algorithms: Designed to arrange elements in a specific order, typically numerical or alphabetical, with common use cases for providing ascending or descending outputs.

Standard Algorithms Include:
- Bubble Sort: A straightforward sorting method that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order.
- Insertion Sort: A sorting algorithm that builds a sorted array one element at a time, inserting each new element into its correct position.
- Merge Sort: A more efficient algorithm that uses a divide-and-conquer approach to sort elements.
- Quick Sort: Utilizes a pivot element to partition the array into lesser and greater elements, then sorts sub-arrays recursively.

Operation:
- Compares each pair of adjacent elements.
- Swaps elements if they are in the wrong order, placing the largest unsorted element at the end of the list with each pass.
- Pseudocode:
```
A = Array of data
for i = 0 to A.length - 1:
    for j = 0 to A.length - 2:
        if A[j] > A[j+1]:
            Swap A[j] and A[j+1]
return A
```
Example Execution: Sorting the array [4, 9, 1, 6, 7] through iterative passes where two elements are compared and swapped as needed.
Efficiency: Bubble sort is slow, making many pointless comparisons; however, modifications can halt execution early if no swaps occur in a pass.

Operation:
- Starts with the second element and builds a sorted portion by placing each new element into its correct position within the previously sorted section.
- Pseudocode:
```
A = Array of data
for i = 1 to A.length - 1:
    elem = A[i]
    j = i - 1
    while j >= 0 and A[j] > elem:
        A[j+1] = A[j]
        j = j - 1
    A[j+1] = elem
```
Example Execution: Starting with the list [4, 9, 1, 6, 7]; elements are moved left to create a sorted array.
Efficiency: Similar to bubble sort in speed.

Operation:
- This divide-and-conquer algorithm recursively splits the input array until each sub-array contains only one element. The merging of these single elements forms back into larger sorted arrays.
- Pseudocode: Not explicitly provided but involves splitting into halves and merging sorted arrays.
Example Execution: The input [7, 4, 2, 6] is divided and merged:
1. Split: [7], [4], [2], [6]
2. Merge: [4, 7], [2, 6]
3. Final Merge: [2, 4, 6, 7]
Efficiency: Faster than bubble and insertion sorts due to reduced comparisons.

Operation:
- Chooses a pivot, partitions the array into elements less than and greater than the pivot, and calls itself recursively on the partitions.
- Old pivots are shaded, indicating they are correctly positioned.
- Example Execution: Using an array [2, 8, 9, 6, 3, 7, 1] with pivot 6, elements will be divided until all elements are sorted into [1, 2, 3, 6, 7, 8, 9].
Efficiency: While the name suggests speed, actual performance can mirror bubble or insertion sort.