Research on the Amount of Information Needed to Restore the Original Order of Four or Eight Elements Lists, when Using Different Sorting Algorithms

Abstract

Data sorting is essential in most software applications, but sometimes elements need to be restored to their original order after processing. If this restoration happens long after sorting or on a different computer, additional information is needed to restore the order. This work explores the information needed to restore sequences of 4 and 8 elements. The following sorting algorithms were studied: parallel neighbour (odd even) sort, insertion sort, bubble sort, shell sort, merge-insertion sort, and merge sort. For each algorithm, the amount of information required in bytes to restore the original order of the elements was determined.