Internal sorting algorithms sort the data while it is entirely in the main memory, which is suitable for smaller datasets that can fit in RAM. Examples include bubble sort, insertion sort, merge sort, quick sort, and heap sort. They are generally faster due to the speed of accessing data in main memory. Conversely, external sorting algorithms are employed when the data set is too large to fit into the main memory and rely on auxiliary storage devices such as hard drives, which makes them slower due to the I/O operations involved. An example of this is the address calculation sort. Choosing between internal and external sorting depends primarily on the data set size relative to the available main memory .

Heap sort organizes data into a binary heap structure—typically a max-heap for ascending sort or a min-heap for descending sort—where the root node is the maximum or minimum element. The algorithm involves repeatedly removing the root, which is the current max (or min), and restructuring the heap to maintain its properties. This results in an O(n log n) time complexity due to the overhead of maintaining the heap after each extraction. Benefits of heap sort include its in-place nature and pattern independence, while drawbacks include higher constant factors and potential inefficiency compared to algorithms like quick sort or merge sort in systems where recursive strategies are optimized better .

Handling datasets with many duplicate keys in quick sort can lead to unbalanced partitions and, consequently, higher time complexity. To mitigate this, modifications such as the 'three-way' quick sort can be employed, which involves partitioning the array into three sections: elements less than the pivot, elements equal to the pivot, and elements greater than the pivot. This helps effectively deal with duplications by reducing redundant comparisons and swaps among duplicate keys, thus improving the performance especially in datasets with numerous duplicate keys by bringing the effective time complexity closer to O(n log n) even in the presence of duplicates .

Bubble sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order, which can lead to inefficiencies with time complexity of O(n^2). Insertion sort, however, builds the sorted output one element at a time by repeatedly picking the next element and inserting it into its correct position within the already sorted portion. It's more efficient on smaller datasets and partially sorted data with a similar O(n^2) complexity in the worst case but better performance in scenarios where elements are mostly sorted as it leverages the existing order .

Merge sort is preferable when data is stored in a linked list because it requires sequential access, and merge sort’s straightforward merging process suits such structures without needing random access indexing, which is essential for quick sort. Another scenario where merge sort is advantageous is when stable sorting is needed, as merge sort maintains the relative order of equal elements while quick sort does not guarantee stability unless modified. These advantages stem from merge sort’s consistent O(n log n) performance across different data types and its natural adaptation for external sorting needs .

The bubble sort algorithm is stable because, during its swapping operations, it only swaps adjacent elements when necessary, thereby keeping the relative order of keys with equal values unchanged. Stability is crucial in applications where the order of equal elements must be preserved for subsequent processing or when data carries meaningful sequential attributes, such as sorting a table of records where each record contains a timestamp and all records with identical attributes are time-sorted .

The pivot element in quick sort is used as a reference to partition the array such that elements less than the pivot precede it and those greater follow. The choice of pivot significantly impacts the algorithm's efficiency; ideally, the pivot splits the array into two equal halves, minimizing the depth of recursive calls and maintaining O(n log n) efficiency. Poor pivot choice, such as always selecting the first element in already sorted data, results in unbalanced splits, leading to a worst-case time complexity of O(n^2). Efficient pivot selection techniques, like choosing the median-of-three, can help mitigate such issues and optimize performance .

The 'two-way merge' is a key element in merge sort's efficiency as it simplifies the process of merging two sorted lists into a single sorted list, thereby minimizing the number of comparisons needed. Critical steps involved include splitting the dataset into two halves recursively until single-element arrays are obtained, merging these arrays by comparing their elements from both halves, and storing the result in a temporary array. This merge process effectively combines sorted subsets, leveraging the ordering already provided by smaller subsets, which maintains the overall O(n log n) time complexity for merge sort .

Bubble sort has a time complexity of O(n^2), which makes it inefficient on large lists as it requires traversing multiple times depending upon the number of unsorted elements. Quick sort, on the other hand, has an average time complexity of O(n log n) and a worst-case complexity of O(n^2); however, it is generally more efficient than bubble sort for large datasets due to its recursive partitioning strategy. Quick sort is often preferred for large arrays where the additional overhead of recursion can be offset by fewer swaps and comparisons compared to bubble sort .

Heap sort offers in-place sorting with a time complexity of O(n log n), making it more predictable in terms of performance for large datasets since it doesn't depend on pivot choice like quick sort does. However, it typically performs slower in practice due to more complex data structure manipulations and cache inefficiencies associated with tree traversal. Quick sort, while recursive and slower in worst-case scenarios, often benefits from better cache performance and average case efficiency with a space complexity benefit over recursive stack overhead when optimized with tail-call eliminations or iterative implementations. Each algorithm's practical use is context-dependent: heap sort is ideal where in-place consistency and predictability matter more, while quick sort is favorable in optimized environments where average-case performance is prioritized .