Реалізація паралельного алгоритму сортування 3-WAY Merge Sort

Abstract

У роботі розглянуто розробку та дослідження ефективності паралельного алгоритму сортування масивів даних на основі тришляхового алгоритму злиття 3-way Merge Sort. Проаналізовано особливості послідовних та паралельних методів сортування, проведено огляд відомих підходів до розпаралелювання рекурсивних алгоритмів, а також обґрунтовано вибір засобів програмної реалізації. У роботі розроблено програмний модуль на мові програмування C#, створено та описано алгоритмічну структуру сортування, реалізовано механізм адаптивного переходу між послідовним та паралельним виконанням на основі порогового значення. Проведено тестування швидкодії, побудовано графіки порівняння часу виконання паралельного і послідовного сортування. Реалізація програмного модуля дозволяє підвищити продуктивність опрацювання великих обсягів даних за рахунок ефективного використання багатопотоковості. Одержані результати можуть бути використані в системах обробки даних, високопродуктивних програмних комплексах та навчальних проектах, що вимагають оптимізації алгоритмів сортування.

The paper examines the development and performance evaluation of a parallel sorting algorithm for data arrays based on the three-way merge sorting technique (3-way Merge Sort). The features of sequential and parallel sorting methods are analyzed, an overview of known approaches to parallelizing recursive algorithms is provided, and the choice of software implementation tools is justified. A software module was developed in the C# programming language, the algorithmic structure of sorting was created and described, and a mechanism for adaptive switching between sequential and parallel execution based on a threshold value was implemented.