Merge sort achieves better time complexity by employing a divide-and-conquer strategy. It recursively divides the array into halves until each sub-array contains a single element or is empty. Then, it merges these sub-arrays back together in order such that each merge operation results in a sorted order. This recursive division and merging result in a consistent time complexity of O(n log n), superior to the O(n^2) time complexity of simple iterative algorithms like bubble or insertion sort .

The 'divide and conquer' concept in algorithms involves breaking a problem into smaller sub-problems, solving each independently, and then combining solutions for the final result. In merge sort, the array is recursively divided into two halves until each half is a single element; the 'conquer' phase merges these single elements into sorted sub-arrays using the merge function. Similarly, quick sort uses a pivot to divide the array into two partitions: items less than the pivot on one side and items more significant on the other, recursively sorting each partition. Both methods utilize 'divide and conquer' to break down and efficiently solve the sorting problem, although quick sort partitions the array during the divide phase itself .

Linear search is less efficient compared to binary search, especially in large datasets, because it involves checking each element of the array sequentially from the beginning until the target element is found or the entire array is traversed, resulting in a time complexity of O(n). In contrast, binary search takes advantage of the sorted nature of arrays, effectively cutting the search space in half with each comparison, resulting in a significantly more efficient O(log n) time complexity. This difference becomes particularly pronounced in large datasets where binary search can dramatically reduce the number of comparisons needed .

Bubble sort and selection sort differ in their approach: bubble sort repeatedly compares and swaps adjacent pairs of elements to "bubble" the largest unsorted element to its correct position at the array's end, while selection sort repeatedly selects the smallest (or largest) unsorted element and swaps it with the first unsorted element in the array. Despite their different approaches, both share the same computational efficiency of O(n^2) for average and worst cases, making them unsuitable for large datasets but easy to implement and understand .

The primary advantage of using insertion sort for partially sorted arrays is its efficiency in handling data that is almost sorted. In such cases, insertion sort can achieve an optimal time complexity of O(n) because it iterates through the array while maintaining a sorted subarray and needs to perform minimal or no shifts for elements that are already in order. This makes it particularly useful for real-time applications that frequently receive new data and require the list to remain partially sorted, outperforming other elementary sorting algorithms like bubble sort which generally operate at O(n^2).

Binary search minimizes the number of comparisons by repeatedly dividing the sorted array in half and comparing the target element with the middle element of each half. If the target element is equal to the middle element, the search is complete. If the target element is less, the search continues in the left half, discarding the right half. Conversely, if the target element is greater, the search continues in the right half. This halving process logarithmically reduces the number of elements to be considered, leading to a time complexity of O(log n).

The pivot element in quick sort plays a critical role by determining the division of elements into two sub-arrays. Elements less than the pivot are placed to its left, and those greater are placed to its right. This partitioning process is crucial for sorting and directly affects the efficiency of quick sort. Ideally, the pivot should divide the array into two equal halves to achieve optimal O(n log n) time complexity. However, the choice of pivot can lead to uneven splits and result in the worst-case time complexity of O(n^2), as in the case of already sorted or reverse-sorted arrays with the first or last element as a pivot .

The average-case time complexity of quick sort is O(n log n), making it very efficient for sorting. This assumes that the pivot divides the list into two roughly equal halves. The worst-case time complexity, however, is O(n^2), which occurs when the pivot ends up being the smallest or largest element consistently, as can happen when the array is already or nearly sorted. The primary factor influencing this difference is the choice of pivot: a poor choice, such as always picking the first or last element, can lead to unbalanced partitions and thus worse performance. Using techniques like the median-of-three rule for pivot selection can help mitigate these inefficiencies .

Bubble sort and insertion sort differ in terms of efficiency and operation. Bubble sort repeatedly steps through the array, compares adjacent elements, and swaps them if they are in the wrong order, resulting in a time complexity of O(n^2) on average and in the worst case. Conversely, insertion sort builds the sorted array one element at a time, moving the current element to its correct position in a sorted portion, also resulting in a time complexity of O(n^2) overall, but it can be more efficient for small or partially sorted arrays as it has a best-case time complexity of O(n) when the array is already sorted .

Selection sort is particularly useful in scenarios where memory usage is critical because it performs sorting with a constant amount of additional space (O(1) space complexity). Even though selection sort has a time complexity of O(n^2), making it inefficient for large lists, its minimal memory usage makes it suitable for embedded systems or applications where space is a bigger constraint than time .