Performance tests on merge sort and recursive merge sort for big data processing
Zbigniew Marszałek
Abstrakt
Merge sort algorithm is widely used in databases to organize and search for information. In the work the author describes some newly proposed not recursive version of the merge sort algorithm for large data sets. Tests of the algorithm confirm the effectiveness of the method and the stability of the proposed version.
Słowa kluczowe:
software, dependability, workflow, analysis of computer algorithms, big data, merge sortBibliografia
ARTIEMJEW P., NOWAK B., POLKOWSKI L. 2016. A New Classifier Based on the Dual Indiscernibility Matrix. In: Information and Software Technologies. Eds. G. Dregvaite, R. Damasevicius. Communications in Computer and Information Science, 639: 380–391.
AUMULLER M., DIETZFELBINGER M. 2013 Optimal Partitioning for Dual Pivot Quicksort. ICALP’13 Proceedings of the 40th international conference on Automata, Languages, and Programming. Part I. Eds. F.V. Fomin, R. Freivalds, M. Kwiatkowska, D. Peleg. Springer-Verlag Berlin, Heidelberg.
AUMULLER M., DIETZFELBINGER M., KLAUE P. 2016. How Good Is Multi-Pivot Quicksort? ACM Trans.Algorithms, 13(1): 47.
DAMASEVICIUS R., MASKELIUNAS R., VENCKAUSKAS R., WOŹNIAK M. 2016a. Smartphone User Identity Verification Using Gait Characteristics. Symmetry 8(10): 100. doi: 10.3390/sym8100100.
DAMASEVICIUS R., VASILJEVAS M., SALKEVICIUS J., WOZNIAK M. 2016b. Human Activity Recognition in AAL Environments Using Random Projections. Comp. Math. Methods in Medicine, 2016(ID4073584): 17. http://dx.doi.org/10.1155/2016/4073584.
GABRYEL M. 2016. The Bag-of-Features Algorithm for Practical Applications Using the MySQL Database. Lecture Notes in Computer Science – ICAISC, 9693: 635–646. doi: 10.1007/978-3-319-39384-1.
GRYCUK R., GABRYEL M., SCHERER R., VOLOSHYNOVSKIY S. 2015. Multi-layer Architecture For Storing Visual Data Based on WCF and Microsoft SQL Server Database. Lecture Notes in Computer Science – ICIST, 9119: 715–726. doi: 10.1007/978-3-319-19324-3.
MARSZAŁEK Z., WOŹNIAK G., BOROWIK M., WAZIRALI R., NAPOLI C., PAPPALARDO G., TRAMONTANA E. 2015. Benchmark tests on improved merge for big data processing. Asia-Pacific Conference on Computer Aided System Engineering APCASE’2015, 14–16 July, Quito, Ecuador, pp. 96–101. IEEE. doi: 10.1109/APCASE.2015.24.
MARSZAŁEK Z., POŁAP D., WOŹNIAK M. 2014. On preprocessing large data sets by the use of triple merge sort algorithm. Proceedings of International Conference on Advances in Information Processing and Communication Technologies – IPCT’2014, 7–8 June, Rome, Italy, pp. 65–72. The IRED, Seek Digital Library. doi: 10.15224/978-1-63248-021-7-78.
MARSZAŁEK Z. 2017. Performance test on triple heap sort algorithm. Technical Sciences, 20(1): 49–61.
MARSZAŁEK Z. 2016. Novel Recursive Fast Sort Algorithm. Communications in Computer and Information Science – ICIST, 639: 344–355. doi: 10.1007/978-3-319-46254-7.
MARSZAŁEK Z. 2017. Parallelization of Modified Merge Sort Algorithm. Symmetry, 9(9): 176:1-176:18. doi: 10.3390/sym9090176.
MLECZKO W.K., NOWICKI R.K., ANGRYK R.A. 2016. Rough Restricted Boltzmann Machine – New Architecture for Incomplete Input Data. Lecture Notes in Computer Science-ICAISC, 9692: 114–125. doi: 10.1007/978-3-319-39378-0.
NEBEL M.E., WILD S., MARTINEZ C. 2016. Analysis of Pivot Sampling in Dual-Pivot Quicksort: A Holistic Analysis of Yaroslavskiy;s Partitioning Scheme. Algorithmica, 75(4): 632–683.
NOWICKI R.K., SCHERER R., RUTKOWSKI L. 2016. Novel rough neural network for classification with missing data. 21st International Conference on Methods and Models in Automation and Robotics, MMAR, Miedzyzdroje, August 29 – September 1, IEEE, p. 820–825. doi: 10.1109/MMAR.2016.7575243.
WENGER L.M., TEUCHOLA J.I. 1989. The External Heapsort. IEEE Transactions on Software Engineering, 15(7).
WOŹNIAK M., MARSZAŁEK Z., GABRYEL M., NOWICKI R.K. 2013. On quick sort algorithm performance for large data sets. In: Looking into the Future of Creativity and Decision Support Systems. Ed. A.M.J. Skulimowski. Progress & Business Publishers, 7–9: 647–656.
WOŹNIAK M., MARSZAŁEK Z., GABRYEL M., NOWICKI R.K. 2016. Preprocessing Large Data Sets by the Use of Quick Sort Algorithm. Advances in Intelligent Systems and Computing – KICSS, 364: 111–121. doi: 10.1007/978-3-319-19090-7.
WOŹNIAK M., MARSZAŁEK Z., GABRYEL M., NOWICKI R.K. 2013. Triple heap sort algorithm for large data sets. In: Looking into the Future of Creativity and Decision Support Systems. Ed. A.M.J. Skulimowski. Progress & Business Publishers, 7–9: 657–665.
WOŹNIAK M., MARSZAŁEK Z., GABRYEL M., NOWICKI R.K. 2013. Modified merge sort algorithm for large scale data sets. Leure Notes in Artificial Intelligence – ICAISC’2013, 7895, 612–622. doi: 10.1007/978-3642-38610-756.
ŻMUDZIŃSKI L., ARTIEMJEW P. 2017. Path Planning Based on Potential Fields from Rough Mereology. IJCRS, 2: 158–168.
WILD S., NEBEL M.E., MAHMOUD H. 2016. Analysis of Quickselect Under Yaroslavskiy’s Dual-Pivoting Algorithm. Algorithmica, 74(1): 485–506.
AUMULLER M., DIETZFELBINGER M. 2013 Optimal Partitioning for Dual Pivot Quicksort. ICALP’13 Proceedings of the 40th international conference on Automata, Languages, and Programming. Part I. Eds. F.V. Fomin, R. Freivalds, M. Kwiatkowska, D. Peleg. Springer-Verlag Berlin, Heidelberg.
AUMULLER M., DIETZFELBINGER M., KLAUE P. 2016. How Good Is Multi-Pivot Quicksort? ACM Trans.Algorithms, 13(1): 47.
DAMASEVICIUS R., MASKELIUNAS R., VENCKAUSKAS R., WOŹNIAK M. 2016a. Smartphone User Identity Verification Using Gait Characteristics. Symmetry 8(10): 100. doi: 10.3390/sym8100100.
DAMASEVICIUS R., VASILJEVAS M., SALKEVICIUS J., WOZNIAK M. 2016b. Human Activity Recognition in AAL Environments Using Random Projections. Comp. Math. Methods in Medicine, 2016(ID4073584): 17. http://dx.doi.org/10.1155/2016/4073584.
GABRYEL M. 2016. The Bag-of-Features Algorithm for Practical Applications Using the MySQL Database. Lecture Notes in Computer Science – ICAISC, 9693: 635–646. doi: 10.1007/978-3-319-39384-1.
GRYCUK R., GABRYEL M., SCHERER R., VOLOSHYNOVSKIY S. 2015. Multi-layer Architecture For Storing Visual Data Based on WCF and Microsoft SQL Server Database. Lecture Notes in Computer Science – ICIST, 9119: 715–726. doi: 10.1007/978-3-319-19324-3.
MARSZAŁEK Z., WOŹNIAK G., BOROWIK M., WAZIRALI R., NAPOLI C., PAPPALARDO G., TRAMONTANA E. 2015. Benchmark tests on improved merge for big data processing. Asia-Pacific Conference on Computer Aided System Engineering APCASE’2015, 14–16 July, Quito, Ecuador, pp. 96–101. IEEE. doi: 10.1109/APCASE.2015.24.
MARSZAŁEK Z., POŁAP D., WOŹNIAK M. 2014. On preprocessing large data sets by the use of triple merge sort algorithm. Proceedings of International Conference on Advances in Information Processing and Communication Technologies – IPCT’2014, 7–8 June, Rome, Italy, pp. 65–72. The IRED, Seek Digital Library. doi: 10.15224/978-1-63248-021-7-78.
MARSZAŁEK Z. 2017. Performance test on triple heap sort algorithm. Technical Sciences, 20(1): 49–61.
MARSZAŁEK Z. 2016. Novel Recursive Fast Sort Algorithm. Communications in Computer and Information Science – ICIST, 639: 344–355. doi: 10.1007/978-3-319-46254-7.
MARSZAŁEK Z. 2017. Parallelization of Modified Merge Sort Algorithm. Symmetry, 9(9): 176:1-176:18. doi: 10.3390/sym9090176.
MLECZKO W.K., NOWICKI R.K., ANGRYK R.A. 2016. Rough Restricted Boltzmann Machine – New Architecture for Incomplete Input Data. Lecture Notes in Computer Science-ICAISC, 9692: 114–125. doi: 10.1007/978-3-319-39378-0.
NEBEL M.E., WILD S., MARTINEZ C. 2016. Analysis of Pivot Sampling in Dual-Pivot Quicksort: A Holistic Analysis of Yaroslavskiy;s Partitioning Scheme. Algorithmica, 75(4): 632–683.
NOWICKI R.K., SCHERER R., RUTKOWSKI L. 2016. Novel rough neural network for classification with missing data. 21st International Conference on Methods and Models in Automation and Robotics, MMAR, Miedzyzdroje, August 29 – September 1, IEEE, p. 820–825. doi: 10.1109/MMAR.2016.7575243.
WENGER L.M., TEUCHOLA J.I. 1989. The External Heapsort. IEEE Transactions on Software Engineering, 15(7).
WOŹNIAK M., MARSZAŁEK Z., GABRYEL M., NOWICKI R.K. 2013. On quick sort algorithm performance for large data sets. In: Looking into the Future of Creativity and Decision Support Systems. Ed. A.M.J. Skulimowski. Progress & Business Publishers, 7–9: 647–656.
WOŹNIAK M., MARSZAŁEK Z., GABRYEL M., NOWICKI R.K. 2016. Preprocessing Large Data Sets by the Use of Quick Sort Algorithm. Advances in Intelligent Systems and Computing – KICSS, 364: 111–121. doi: 10.1007/978-3-319-19090-7.
WOŹNIAK M., MARSZAŁEK Z., GABRYEL M., NOWICKI R.K. 2013. Triple heap sort algorithm for large data sets. In: Looking into the Future of Creativity and Decision Support Systems. Ed. A.M.J. Skulimowski. Progress & Business Publishers, 7–9: 657–665.
WOŹNIAK M., MARSZAŁEK Z., GABRYEL M., NOWICKI R.K. 2013. Modified merge sort algorithm for large scale data sets. Leure Notes in Artificial Intelligence – ICAISC’2013, 7895, 612–622. doi: 10.1007/978-3642-38610-756.
ŻMUDZIŃSKI L., ARTIEMJEW P. 2017. Path Planning Based on Potential Fields from Rough Mereology. IJCRS, 2: 158–168.
WILD S., NEBEL M.E., MAHMOUD H. 2016. Analysis of Quickselect Under Yaroslavskiy’s Dual-Pivoting Algorithm. Algorithmica, 74(1): 485–506.
Marszałek, Z. (2017). Performance tests on merge sort and recursive merge sort for big data processing. Technical Sciences, 21(1), 19–35. https://doi.org/10.31648/ts.2714
Zbigniew Marszałek
