Sorting and Search Algorithms

Data retrieval efficiency depends significantly on whether data is sorted. Unsorted data requires more time and space to process compared to sorted data.
A successful search operation is referred to as retrieval, which returns the desired record or a pointer to it.
Failed searches result in a null record or a null pointer.

Operates on the divide and conquer principle by subdividing a list and sorting it recursively.
The midpoint is determined by the formula $mid = (First + Last) / 2$ .
Sub-lists $A[First...mid]$ and $B[mid + 1...Last]$ are sorted separately and then combined to form the final sorted list.

Utilizes a pivot element $v$ to partition an unsorted list $I$ into two sub-lists, $I1$ and $I2$ .
Sub-list $I1$ contains keys smaller than the pivot, while $I2$ contains keys larger than the pivot.
The algorithm recursively sorts $I1$ and $I2$ into $S1$ and $S2$ , then concatenates $S1$ , $v$ , and $S2$ to produce the final list $S$ .

Involves multiple sequential passes through a file.
In each pass, adjacent elements $x[i]$ and $x[i+1]$ are compared and interchanged if they are out of order.
The process iterates until the entire list is sorted, with the largest elements "bubbling" to their final positions in each pass.

Each item from an unsorted list $I$ is added to a sequence $S$ one at a time.
Items are inserted into $S$ at specific positions to maintain continuous sorted order.
The process repeats until the original list $I$ is empty.

Scans an array of $n$ items to identify the smallest element, defined as $Min[x[i]]$ .
The smallest element is swapped into its correct place at the beginning of the current sub-array.
The algorithm then repeats this scan for the remaining $n - 1$ items until the entire list is sorted.

A specialized version of selection sort that utilizes a heap structure.
The largest element $Max[X[i]]$ is removed from the heap and placed into a new sorted list.
This step repeats until all elements have been transferred from the heap to the new list.

Used when the array size is known; the data does not require prior sorting.
The algorithm sequentially examines every index starting from $counter = 0$ .
If the search element matches the list element at the current counter, that index is returned.
If the search concludes without a match, the value $-1$ is returned.

Designed for high-speed retrieval from lists sorted in ascending or descending order.
The algorithm determines the middle position using $mid = (first + last) / 2$ .
If the target is not at the midpoint, the search space is halved:
- If the search element is less than the midpoint element, the new boundary becomes $last = mid - 1$ .
- If the search element is greater than the midpoint element, the new boundary becomes $First = mid + 1$ .

Describe the following sort algorithms: Merge sort, Quick sort, Bubble sort, Insertion sort, Selection sort, and Heap sort.
Write down an algorithm for each of the sort types listed above.
State one limitation and one strength for each of the sorting algorithms.
Use the described algorithms to sort the following numerical lists:
- $9, 6, 1, 8, 2, 4, 3, 10, 18, 11, 14, 16$
- $1000, 700, 1200, 300, 800, 600, 1700, 1100, 1300, 2000$
Use the linear search algorithm to find the element $7$ within the list $8, 6, 0, 5, 10, 3, 7$ .
Using the sorted list $3, 4, 7, 9, 12, 20, 36, 38, 40$ , perform a binary search for the element $36$ .