Halstead's Complexity Measure of a Merge Sort and Modified Merge Sort Algorithms

Ghaniyyat Bolanle Balogun, Muhideen Abdulraheem, Peter Ogirima Sadiku, Olawale Debo Taofeek, Adebisi Sodiq Adewale

Abstract


Complexity measuring tools in computer science are deployed to measure and compare different characteristics of algorithms to find the best one to solve a particular problem or that suits a specific situation. Also,  this is used to measure the complexity of a software program without running the program itself. Given this, Halstead's complexity metrics are deployed to compare the efficiency of two external sorting methods: the Merge Sort and the Modified Merge Sort Algorithms. The methodology used in achieving this lies in extracting operators and operands from the C_sharp (C#) implemented program of the two algorithms. Six Halstead metrics are evaluated using these operators and operands as parameters. The results show that the modified merge sort algorithm is much more efficient than the conventional Merge sort as it has a lower Program Volume, Program Difficulty, and Program Effort even though the advantage of a higher Intelligence content goes to the merge sort algorithm.

Keywords


Algorithms; Complexity measure; Halstead metrics; Modified merge sort algorithms

Full Text:

PDF (ENGLISH)

References


Balogun, G. B. (2019). A modified linear search algorithm. African Journal of Computer Science & ICT, 12(2), 43-54.

Balogun, G. B., Olanrewaju, B. A., Awotunde, J. B., Oladipo, I. D., & AbdulRaheem, M. (2021). Evaluating the time efficiency of a modified merge sort algorithm. Bulletin of the Science Association of Nigeria. 32. 141-159.

Diego, L. Y. (2020). Time complexity: how to measure the efficiency of algorithms. Retrieved February 2022 from https://www.kdnuggets.com/2020/06/time-complexity-measure-efficiency-algorithms.html

GeeksforGeeks (2020). External sorting. Retrieved May 2020 from https://www.geeksforgeeks.org/external-sorting

GeeksforGeeks. Merge sort. Retrieved May 2020 from https://www.geeksforgeeks.org/merge-sort

Hariprasad, T., Vidhyagaran, G., K. Seenu, K., Thirumalai, C. (2017). Software complexity analysis using Halstead metrics. In International Conference on Trends in Electronics and Informatics ICOEI 2017, Tirunelveli, India. doi: 10.1109/ICOEI.2017.8300883

Hassan, A. A., Kvasnikov, A. A., Klyukin, D. V., Ivanov, A. A., Demakov, A. V., Mochalov, D. M., & Kuksenko, S.P. (2023). On modeling antennas using mom-based algorithms: Wire-grid versus surface triangulation. Algorithms, 16(4), 200. doi: 10.3390/a16040200

InterviewBit. Merge sort algorithm. Retrieved May 2020 from https://www.interviewbit.com/tutorial/merge-sort-algorithm

Irfan, A., Haque, N., Imran, K., Ameen, M.C., & Malook, M.R. (2018). Performance comparison between merge and quick sort algorithms in data structure. International Journal of Advanced Computer Science and Applications (IJACSA), 9(11), 192-195. doi: 10.14569/IJACSA.2018.091127

Maushumi, L. & Uzzal S. (2019). Complexity assessment based on UML-activity diagram. International Journal of Recent Technology and Engineering (IJRTE), 8(2), 6117-6122.

Mohammad S. & Ashok K. (2019). A novel sorting technique for large-scale data. Journal of Computer Networks and Communications, 1(1), 1-7.

Open DSA (2019). CS 3. Data structures and algorithms. External sorting. Retrieved May 2020 from https://opendsa-server.cs.vt.edu/ODSA/Books/CS3/html/ExternalSort.html

Programiz. (2020). Merge sort algorithm. Retrieved May 2020 from https://www.programiz.com/dsa/merge-sort

Rabiu, A. M., Garba, E. J., Baha, B. Y., & Mukhtar, M. I. (2021). Comparative analysis between selection sort and merge sort algorithms. Nigerian Journal of Basic and Applied Sciences, 29(1), 43-48. doi: 10.4314/njbas.v29i1.5

Rajagopal, D., & Thilakavalli, K. (2016). Different sorting algorithm's comparison based upon the time complexity. International Journal of U- and e-Service, Science and Technology, 9(8), 287-296. doi: 10.14257/ijunesst.2016.9.8.24

Senan, S., & Sevgen, S. (2017). Measuring software complexity using neural networks. Journal of Electrical and Electronics Engineering, 17(2), 3503-3508.

Shabaz, M., & Kumar, A. (2019). SA sorting: A novel sorting technique for large-scale data. Journal of Computer Networks and Communications. doi: 10.1155/2019/3027578

Sharma, C. B. Panwar and R. Arya (Diego, 2022). High power pulsed current laser diode driver. In International Conference on Electrical Power and Energy Systems (ICEPES), Bhopal, India, 1(1), 120-126, doi: 10.1109/ICEPES.20A

Taiwo, O. E., Christianah, A. O., Oluwatobi, A. N., & Aderonke, K. A. (2020). Comparative study of two divide and conquer sorting algorithms: Quicksort and mergesort. Procedia Computer Science, 171, 2532-2540. doi: 10.1016/j.procs.2020.04.274

Yadav, R., & Varshney, K. (2014). Brief study about the variation of complexities in algorithmic merge sort. International Journal of Advanced Research in Computer Science and Software Engineering, 4(2), 874-878.




DOI: https://doi.org/10.37905/jji.v5i2.21995

Refbacks

  • There are currently no refbacks.


JJIhas been indexed by:
Sinta Crossref Scholar Garuda
Base Dimension ROAD SIS
ASCI







Editorial Office
Department of Informatics Engineering, Universitas Negeri Gorontalo
Engineering Faculty Building, 1st Floor
Jl. Prof. Dr. Ing. B. J. Habibie, Bone Bolango, Gorontalo, 96119, Indonesia. Whatsapp: +6281314270499 Email: jji.ft@ung.ac.id
Creative Commons Licence
Jambura Journal of Informatics (JJi), is licensed under a Lisensi Creative Commons Atribusi 4.0 Internasional.