What is the primary advantage of using a multiway merge sort over a standard two-way merge sort in external sorting?
Simplified implementation
Reduced memory consumption
Improved time complexity in all cases
Minimized disk I/O operations
In external sorting, what is a 'run' in the context of multiway merge sort?
The final merged and sorted output
The total number of sorted files
A portion of the data that is sorted in memory
A single element in the unsorted data
How does parallel merge sort leverage multiple cores for improved performance?
It uses a single core for sorting but multiple cores for data I/O
It divides the data, sorts sub-arrays concurrently, then merges the results
It assigns each element to a separate core for independent sorting
It employs a different sorting algorithm on each core for diversity
Which of the following scenarios would be an ideal use case for external sorting?
Reordering a linked list in a real-time graphics engine
Sorting a small array of integers within a mobile app
Generating a leaderboard from a massive online gaming database
Sorting a list of recently accessed files by timestamp
Which of these applications is LEAST likely to benefit significantly from parallel sorting?
Climate modeling simulations on a supercomputer
Analyzing large-scale genomic data for disease research
Real-time fraud detection in financial transactions
Sorting a small list of contacts in a mobile phone app
In parallel quick sort, what is the impact of choosing a pivot element on performance?
The pivot should always be the first element in each partition
A poorly chosen pivot can lead to unbalanced workloads across cores
Pivot selection is irrelevant in a parallel context
Only a randomly chosen pivot guarantees optimal parallel efficiency
During the merging process in Timsort, what data structure is commonly used to efficiently combine the sorted 'runs'?
A queue
A stack
A linked list
A temporary array
In external sorting, why is it common to divide the input data into chunks that fit in memory?
To distribute the sorting workload across multiple processors.
To minimize the number of files needed for intermediate results.
To enable the use of faster in-memory sorting algorithms.
To reduce the complexity of the sorting algorithm.
What is the worst-case time complexity of Timsort, and how does it compare to the worst-case complexities of Merge sort and Insertion sort?
Timsort: O(n^2), Merge sort: O(n log n), Insertion sort: O(n^2)
Timsort: O(n), Merge sort: O(n log n), Insertion sort: O(n)
Timsort: O(n log n), Merge sort: O(n^2), Insertion sort: O(n log n)
Timsort: O(n log n), Merge sort: O(n log n), Insertion sort: O(n^2)
Why are distributed systems often well-suited for implementing parallel sorting algorithms?
They provide a natural way to divide data and processing across multiple nodes
Network latency is negligible in modern distributed systems
Distributed systems inherently prevent data races in parallel processing
Distributed systems automatically choose the optimal sorting algorithm