The thesis presents data sorting on external storage devices such as hard drives and tape drives. The theoretical part describes several different algorithms and their basic principles of operation, as well as their main advantages and disadvantages. For the comparison, the listed algorithms were selected: straight merge sort, natural balanced two-way merge sort, natural balanced multi-way merge sort, polyphase merge sort and triton sort. The practical part compares the selected algorithms by their runtime, the number of element compares, the amount of data read from the hard drive and amount of data written to the hard drive. We compared the algorithms on two different types of input data: 32-bit integers and strings of random length, as well as five different initial distributions of input data. The random, Gaussian, partly ordered, ordered and inverse ordered distribution were chosen. The algorithms were implemented in Java programming language and run on a personal computer with Linux operating system and one hard drive.
|
