Study of the efficiency of some deterministic preprocessing methods for sorting algorithms

V.I. Shynkarenko, O.V. Makarov


To verify the hypothesis about decrease in time of sorting by algorithms of different computational complexity experiments have been conducted. Several ideas on deterministic preprocessing of data arrays for sorting algorithms have been tested. The following algorithms are proposed: quick preprocessing – prediction of the index of an element in a sorted array and permutation, preprocessing with memory - prediction and permutation with memorization of previously set elements, preprocessing with reordering – reverting sequences of elements sorted in reverse order. Also proposed block variations of quick and preprocessing with memory, which are performed for parts of the array of a given length. It has been defined that the higher efficiency of preprocessing is achieved by using with sorting algorithms, which are significantly accelerated on sorted (or almost sorted) arrays of data. Block preprocessing methods can be performed faster due to the possibility of avoiding cache misses, but show a lower percentage of array sorting. Experiments were conducted to evaluate the effectiveness of various sorting algorithms after and together with the proposed preprocessing methods.

Prombles in programming 2023; 4: 3-14


sorting algorithm; sorting; time efficiency; combined algorithm; preprocessing


Knuth, Donald. The Art Of Computer Programming, vol. 3: Sorting And Searching. : Addison-Wesley, 1973.

Timsort [Online] - Available from:, last accessed 2023/08/07.

Musser, David R. (1997). "Introspective Sorting and Selection Algorithms". Software: Practice and Experience. 27 (8): 983-993. CrossRef

Adnan Saher Mohammed, Şahin Emrah Amrahov, Fatih V. Çelebi. Bidirectional Conditional Insertion Sort algorithm; An efficient progress on the classical insertion sort. Future Generation Computer Systems, Volume 71, June 2017, 102-112. CrossRef

Shrinu Kushagra, Alejandro López-Ortiz, Aurick Qiao, J. Ian Munro. Multi-Pivot Quicksort: Theory and Experiments. 2014 Proceedings of the Meeting on Algorithm Engineering and Experiments (ALENEX), 47-60 CrossRef

Шинкаренко В.І., Дорошенко А.Ю., Яценко О.А., Разносілін В.В., Галанін К.К. Двокомпонентні алгоритми сортування Проблеми програмування. - 2022. - № 3-4. - С. 32-41. - Бібліогр.: 18 назв. - укр.

Abbas Mubarak, Sajid Iqbal, Qaisar Rasool, Nabeel Asghar, Neetu Faujdar, & Abdul Rauf. (2022). Preprocessing: A method For Reducing Time Complexity. Journal of Computing & Biomedical Informatics, 4(01), 104-117. CrossRef

Шинкаренко В.І Сравнительный анализ временной эффективности функционально эквивалентных алгоритмов / В. И. Шинкаренко // Проблемы программирования. - 2001. - № 3-4. - С. 31-39

Hoare, C. A. R. (1962). "Quicksort". Comput. J. 5 (1): 10-16. CrossRef

Insertion sort [Online] - Available from:, last accessed 2023/08/07.

Knuth, Donald E. (1973). "Sorting by Exchanging". Art of Computer Programming. Vol. 3. Sorting and Searching (1st ed.). Addison-Wesley. pp. 110-111.

Bubble sort [Online] - Available from:, last accessed 2023/08/07.



  • There are currently no refbacks.