Correct and stable sorting for overflow streaming data with a limited storage size and a uniprocessor

Area of Science:

• Computer Science
• Data Science
• Algorithm Design

Background:

• Massive numeric data streams are generated across cyber ecosystems.
• Traditional sorting algorithms fail with streaming data due to storage limitations.
• Data overflow necessitates new approaches for sorting in constrained environments.

Purpose of the Study:

• To propose a new sorting algorithm, "streaming data sort," for uniprocessor systems with limited storage.
• To address the challenge of sorting data streams that exceed available memory.
• To ensure the correctness of the sorted order despite storage constraints.

Main Methods:

• Developed a "streaming data sort" algorithm designed for continuous data flow in chunks.
• Conducted theoretical analysis of space and time complexity for the proposed algorithm.
• Performed experiments to validate the algorithm's performance with large datasets.

Main Results:

• The streaming data sort algorithm achieves a time complexity of O(n), where n is the number of incoming data.
• The space complexity is O(M), where M is the storage size.
• Experimental results demonstrate the ability to sort one million permuted data points using storage as low as 35% of the data size.

Conclusions:

• The proposed "streaming data sort" algorithm is effective for handling data streams that overflow working storage.
• The algorithm offers a practical solution for sorting in resource-constrained environments.
• This approach has broad applicability in fields requiring sorting of massive, continuously generated data.