🧮 Cuda GPU fibonacci Sequence Sorting project

This project is written in C++ on Cuda. The general Idea of this project is to generate a Fibonacci Sequence and sort it by Manual Sorting Algorithms Such as (Bubble Sort, Quick Sort, Merge Sort, and Heap Sort) And Also Sorting Algorithms by Thrust Library such as ('thrust::sort' and 'thrust::transform') at the same time.

We'll see also why a Fibonacci sequence leads to the creation of a - (minus) sequence and how we will handle this.

🗂️ Table of Contents

• What is CUDA parallel programming
• Why we used C++
• What is Fibonacci?
• The Main Idea
• Where did I run this project?
• Some Technical points
• Why minus numbers will be generated?
• How to Run
• My test
• Result Compare
• Conclusion
  
  

🤓 What is CUDA?

CUDA simplifies GPU Parallel programming, allowing developers to utilize the power of NVIDIA GPUs for parallel computing tasks. It provides a programming model, libraries, and tools for efficient GPU acceleration.

🧐 Why do we use C++?

C++ is used with CUDA in this project to take advantage of the rich features and libraries provided by C++. CUDA is an extension of the C++ programming language, allowing developers to write parallel code for GPUs. By using C++, the project can leverage object-oriented programming capabilities, standard template libraries, and other features provided by C++, making the code more expressive, modular, and easier to develop and maintain.

CUDA C is an extension of C specifically designed for GPU programming. While standard C focuses on general-purpose computing, CUDA C is optimized for utilizing the parallel processing capabilities of NVIDIA GPUs.

🧮🔢 What is Fibonacci?

The Fibonacci sequence is a series of numbers in which each number is the sum of the two preceding ones.
It starts with 0 and 1, and the subsequent numbers are generated by adding the two previous numbers together.
The sequence begins as follows: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and so on.
The Fibonacci sequence has many interesting properties and is found in various areas of mathematics, nature, and computer science.

🧭📖 The Main Idea

• At first, we Generate a Fibonacci sequence, The 'N' is the maximum number of the sequence.
  
• Then Is goes to a - (minus) number and - (minus) numbers will generate on the sequence because of the summing of 2 past digits. Why minus numbers will be generated?
  
• After ending the generation process, Sorting Algorithms will be run on the CPU and GPU.
  
• After measuring runtime, the output will be shown.
  
  
  

🏢🚀 Where did I run this project?

IBISCO Clusters (Infrastructure for Big Data and Scientific Computing) of the University of Naples Federico II. IBiSCo

Figure: We have 32 Nodes(servers) on the Data Center, Each node (servers) has 4 GPUs which are connected by nVLink.
These 32 Servers are connected by InfiniBand: Complex workloads demand ultra-fast processing of high-resolution simulations, extreme-size datasets, and highly parallelized algorithms.

📐🧩 Some Technical points

• Manual Sorting algorithms are running on CPUs
• Thrust library sorting algorithms are running on GPU.
• This code will be run on a single GPU. You can modify it to run on more GPUs.
  
  

🔢📉 Why minus numbers will be generated?

Look at the output of the generated sequence:

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 -1323752223 512559680 -811192543 -298632863 -1109825406 -1408458269 1776683621 368225352 2144908973 -1781832971

At this section of the output above:

...    1134903170   1836311903   -1323752223    ...

result of 1134903170 + 1836311903 = 2,971,215,073 Which is Bigger than the Intiger size. As a result, an integer overflow occurs, and the next number becomes a negative number, -1323752223.
From that point on, the generated sequence continues with negative numbers due to the integer overflow caused by adding the previous two numbers.

Then after:

...       ...      1836311903    -1323752223    512559680       ...

And So on:

...       ...          ...       -1323752223    512559680   -811192543    ...

🏁 How to Run

1. You need to implement all 3 files in one directory.

Makefile

simpleKernel.cu

• This file contents the main C++ CUDA parallel programming code.

simpleKernel.sh

• This file is the executer of the project

2. use terminal to go to the project path example:

   cd CUDA/Fibonacci/
   

3. run the code:

   ./simpleKernel.sh 2
   

"2" is the number of threads. You can use 4,8,...

🧑‍🔬📝 My Test:

N = 1000 (Number of Fibonacci sequence)

'Generated Fibonacci Sequence':
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 -1323752223 512559680 -811192543 -298632863 -1109825406 -1408458269 1776683621 368225352 2144908973 -1781832971 363076002 -1418756969 -1055680967 1820529360 764848393 -1709589543 -944741150 1640636603 695895453 -1958435240 -1262539787 1073992269 -188547518 885444751 696897233 1582341984 -2015728079 -433386095 1845853122 1412467027 -1036647147 375819880 -660827267 -285007387 -945834654 -1230842041 2118290601 887448560 -1289228135 -401779575 -1691007710 -2092787285 511172301 -1581614984 -1070442683 1642909629 572466946 -2079590721 -1507123775 708252800 -798870975 -90618175 -889489150 -980107325 -1869596475 1445263496 -424332979 1020930517 596597538 1617528055 -2080841703 -463313648 1750811945 1287498297 -1256657054 30841243 -1225815811 -1194974568 1874176917 679202349 -1741588030 -1062385681 1490993585 428607904 1919601489 -1946757903 -27156414 -1973914317 -2001070731 319982248 -1681088483 -1361106235 1252772578 -108333657 1144438921 1036105264 -2114423111 -1078317847 1102226338 23908491 1126134829 1150043320 -2018789147 -868745827 1407432322 538686495 1946118817 -1810161984 135956833 -1674205151 -1538248318 1082513827 -455734491 626779336 171044845 797824181 968869026 1766693207 -1559405063 207288144 -1352116919 -1144828775 1798021602 653192827 -1843752867 -1190560040 1260654389 70094349 1330748738 1400843087 -1563375471 -162532384 -1725907855 -1888440239 680619202 -1207821037 -527201835 -1735022872 2032742589 297719717 -1964504990 -1666785273 663677033 -1003108240 -339431207 -1342539447 -1681970654 1270457195 -411513459 858943736 447430277 1306374013 1753804290 -1234788993 519015297 -715773696 -196758399 -912532095 -1109290494 -2021822589 1163854213 -857968376 305885837 -552082539 -246196702 -798279241 -1044475943 -1842755184 1407736169 -435019015 972717154 537698139 1510415293 2048113432 -736438571 1311674861 575236290 1886911151 -1832819855 54091296 -1778728559 -1724637263 791601474 -933035789 -141434315 -1074470104 -1215904419 2004592773 788688354 -1501686169 -712997815 2080283312 1367285497 -847398487 519887010 -327511477 192375533 -135135944 57239589 -77896355 -20656766 -98553121 -119209887 -217763008 -336972895 -554735903 -891708798 -1446444701 1956813797 510369096 -1827784403 -1317415307 1149767586 -167647721 982119865 814472144 1796592009 -1683903143 112688866 -1571214277 -1458525411 1265227608 -193297803 1071929805 878632002 1950561807 -1465773487 484788320 -980985167 -496196847 -1477182014 -1973378861 844406421 -1128972440 -284566019 -1413538459 -1698104478 1183324359 -514780119 668544240 153764121 822308361 976072482 1798380843 -1520513971 277866872 -1242647099 -964780227 2087539970 1122759743 -1084667583 38092160 -1046575423 -1008483263 -2055058686 1231425347 -823633339 407792008 -415841331 -8049323 -423890654 -431939977 -855830631 -1287770608 -2143601239 863595449 -1280005790 -416410341 -1696416131 -2112826472 485724693 -1627101779 -1141377086 1526488431 385111345 1911599776 -1998256175 -86656399 -2084912574 2123398323 38485749 -2133083224 -2094597475 67286597 -2027310878 -1960024281 307632137 -1652392144 -1344760007 1297815145 -46944862 1250870283 1203925421 -1840171592 -636246171 1818549533 1182303362 -1294114401 -111811039 -1405925440 -1517736479 1371305377 -146431102 1224874275 1078443173 -1991649848 -913206675 1390110773 476904098 1867014871 -1951048327 -84033456 -2035081783 -2119115239 140770274 -1978344965 -1837574691 479047640 -1358527051 -879479411 2056960834 1177481423 -1060525039 116956384 -943568655 -826612271 -1770180926 1698174099 -72006827 1626167272 1554160445 -1114639579 439520866 -675118713 -235597847 -910716560 -1146314407 -2057030967 1091621922 -965409045 126212877 -839196168 -712983291 -1552179459 2029804546 477625087 -1787537663 -1309912576 1197517057 -112395519 1085121538 972726019 2057847557 -1264393720 793453837 -470939883 322513954 -148425929 174088025 25662096 199750121 225412217 425162338 650574555 1075736893 1726311448 -1492918955 233392493 -1259526462 -1026133969 2009306865 983172896 -1302487535 -319314639 -1621802174 -1941116813 732048309 -1209068504 -477020195 -1686088699 2131858402 445769703 -1717339191 -1271569488 1306058617 34489129 1340547746 1375036875 -1579382675 -204345800 -1783728475 -1988074275 523164546 -1464909729 -941745183 1888312384 946567201 -1460087711 -513520510 -1973608221 1807838565 -165769656 1642068909 1476299253 -1176599134 299700119 -876899015 -577198896 -1454097911 -2031296807 809572578 -1221724229 -412151651 -1633875880 -2046027531 615063885 -1430963646 -815899761 2048103889 1232204128 -1014659279 217544849 -797114430 -579569581 -1376684011 -1956253592 962029693 -994223899 -32194206 -1026418105 -1058612311 -2085030416 1151324569 -933705847 217618722 -716087125 -498468403 -1214555528 -1713023931 1367387837 -345636094 1021751743 676115649 1697867392 -1920984255 -223116863 -2144101118 1927749315 -216351803 1711397512 1495045709 -1088524075 406521634 -682002441 -275480807 -957483248 -1232964055 2104519993 871555938 -1318891365 -447335427 -1766226792 2081405077 

'Bubble' Sort:
-2144101118 -2143601239 -2133083224 -2119115239 -2114423111 -2112826472 -2094597475 -2092787285 -2085030416 -2084912574 -2080841703 -2079590721 -2057030967 -2055058686 -2046027531 -2035081783 -2031296807 -2027310878 -2021822589 -2018789147 -2015728079 -2001070731 -1998256175 -1991649848 -1988074275 -1978344965 -1973914317 -1973608221 -1973378861 -1964504990 -1960024281 -1958435240 -1956253592 -1951048327 -1946757903 -1941116813 -1920984255 -1888440239 -1869596475 -1843752867 -1842755184 -1840171592 -1837574691 -1832819855 -1827784403 -1810161984 -1787537663 -1783728475 -1781832971 -1778728559 -1770180926 -1766226792 -1741588030 -1735022872 -1725907855 -1724637263 -1717339191 -1713023931 -1709589543 -1698104478 -1696416131 -1691007710 -1686088699 -1683903143 -1681970654 -1681088483 -1674205151 -1666785273 -1652392144 -1633875880 -1627101779 -1621802174 -1581614984 -1579382675 -1571214277 -1563375471 -1559405063 -1552179459 -1538248318 -1520513971 -1517736479 -1507123775 -1501686169 -1492918955 -1477182014 -1465773487 -1464909729 -1460087711 -1458525411 -1454097911 -1446444701 -1430963646 -1418756969 -1413538459 -1408458269 -1405925440 -1376684011 -1361106235 -1358527051 -1352116919 -1344760007 -1342539447 -1323752223 -1318891365 -1317415307 -1309912576 -1302487535 -1294114401 -1289228135 -1287770608 -1280005790 -1271569488 -1264393720 -1262539787 -1259526462 -1256657054 -1242647099 -1234788993 -1232964055 -1230842041 -1225815811 -1221724229 -1215904419 -1214555528 -1209068504 -1207821037 -1194974568 -1190560040 -1176599134 -1146314407 -1144828775 -1141377086 -1128972440 -1114639579 -1109825406 -1109290494 -1088524075 -1084667583 -1078317847 -1074470104 -1070442683 -1062385681 -1060525039 -1058612311 -1055680967 -1046575423 -1044475943 -1036647147 -1026418105 -1026133969 -1014659279 -1008483263 -1003108240 -994223899 -980985167 -980107325 -965409045 -964780227 -957483248 -945834654 -944741150 -943568655 -941745183 -933705847 -933035789 -913206675 -912532095 -910716560 -891708798 -889489150 -879479411 -876899015 -868745827 -857968376 -855830631 -847398487 -839196168 -826612271 -823633339 -815899761 -811192543 -798870975 -798279241 -797114430 -736438571 -716087125 -715773696 -712997815 -712983291 -682002441 -675118713 -660827267 -636246171 -579569581 -577198896 -554735903 -552082539 -527201835 -514780119 -513520510 -498468403 -496196847 -477020195 -470939883 -463313648 -455734491 -447335427 -435019015 -433386095 -431939977 -424332979 -423890654 -416410341 -415841331 -412151651 -411513459 -401779575 -345636094 -339431207 -336972895 -327511477 -319314639 -298632863 -285007387 -284566019 -275480807 -246196702 -235597847 -223116863 -217763008 -216351803 -204345800 -196758399 -193297803 -188547518 -167647721 -165769656 -162532384 -148425929 -146431102 -141434315 -135135944 -119209887 -112395519 -111811039 -108333657 -98553121 -90618175 -86656399 -84033456 -77896355 -72006827 -46944862 -32194206 -27156414 -20656766 -8049323 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 23908491 24157817 25662096 30841243 34489129 38092160 38485749 39088169 54091296 57239589 63245986 67286597 70094349 102334155 112688866 116956384 126212877 135956833 140770274 153764121 165580141 171044845 174088025 192375533 199750121 207288144 217544849 217618722 225412217 233392493 267914296 277866872 297719717 299700119 305885837 307632137 319982248 322513954 363076002 368225352 375819880 385111345 406521634 407792008 425162338 428607904 433494437 439520866 445769703 447430277 476904098 477625087 479047640 484788320 485724693 510369096 511172301 512559680 519015297 519887010 523164546 537698139 538686495 572466946 575236290 596597538 615063885 626779336 650574555 653192827 663677033 668544240 676115649 679202349 680619202 695895453 696897233 701408733 708252800 732048309 764848393 788688354 791601474 793453837 797824181 809572578 814472144 822308361 844406421 858943736 863595449 871555938 878632002 885444751 887448560 946567201 962029693 968869026 972717154 972726019 976072482 982119865 983172896 1020930517 1021751743 1036105264 1071929805 1073992269 1075736893 1078443173 1082513827 1085121538 1091621922 1102226338 1122759743 1126134829 1134903170 1144438921 1149767586 1150043320 1151324569 1163854213 1177481423 1182303362 1183324359 1197517057 1203925421 1224874275 1231425347 1232204128 1250870283 1252772578 1260654389 1265227608 1270457195 1287498297 1297815145 1306058617 1306374013 1311674861 1330748738 1340547746 1367285497 1367387837 1371305377 1375036875 1390110773 1400843087 1407432322 1407736169 1412467027 1445263496 1476299253 1490993585 1495045709 1510415293 1526488431 1554160445 1582341984 1617528055 1626167272 1640636603 1642068909 1642909629 1697867392 1698174099 1711397512 1726311448 1750811945 1753804290 1766693207 1776683621 1796592009 1798021602 1798380843 1807838565 1818549533 1820529360 1836311903 1845853122 1867014871 1874176917 1886911151 1888312384 1911599776 1919601489 1927749315 1946118817 1950561807 1956813797 2004592773 2009306865 2029804546 2032742589 2048103889 2048113432 2056960834 2057847557 2080283312 2081405077 2087539970 2104519993 2118290601 2123398323 2131858402 2144908973 

'Merge' Sort:
-2144101118 -2143601239 -2133083224 -2119115239 -2114423111 -2112826472 -2094597475 -2092787285 -2085030416 -2084912574 -2080841703 -2079590721 -2057030967 -2055058686 -2046027531 -2035081783 -2031296807 -2027310878 -2021822589 -2018789147 -2015728079 -2001070731 -1998256175 -1991649848 -1988074275 -1978344965 -1973914317 -1973608221 -1973378861 -1964504990 -1960024281 -1958435240 -1956253592 -1951048327 -1946757903 -1941116813 -1920984255 -1888440239 -1869596475 -1843752867 -1842755184 -1840171592 -1837574691 -1832819855 -1827784403 -1810161984 -1787537663 -1783728475 -1781832971 -1778728559 -1770180926 -1766226792 -1741588030 -1735022872 -1725907855 -1724637263 -1717339191 -1713023931 -1709589543 -1698104478 -1696416131 -1691007710 -1686088699 -1683903143 -1681970654 -1681088483 -1674205151 -1666785273 -1652392144 -1633875880 -1627101779 -1621802174 -1581614984 -1579382675 -1571214277 -1563375471 -1559405063 -1552179459 -1538248318 -1520513971 -1517736479 -1507123775 -1501686169 -1492918955 -1477182014 -1465773487 -1464909729 -1460087711 -1458525411 -1454097911 -1446444701 -1430963646 -1418756969 -1413538459 -1408458269 -1405925440 -1376684011 -1361106235 -1358527051 -1352116919 -1344760007 -1342539447 -1323752223 -1318891365 -1317415307 -1309912576 -1302487535 -1294114401 -1289228135 -1287770608 -1280005790 -1271569488 -1264393720 -1262539787 -1259526462 -1256657054 -1242647099 -1234788993 -1232964055 -1230842041 -1225815811 -1221724229 -1215904419 -1214555528 -1209068504 -1207821037 -1194974568 -1190560040 -1176599134 -1146314407 -1144828775 -1141377086 -1128972440 -1114639579 -1109825406 -1109290494 -1088524075 -1084667583 -1078317847 -1074470104 -1070442683 -1062385681 -1060525039 -1058612311 -1055680967 -1046575423 -1044475943 -1036647147 -1026418105 -1026133969 -1014659279 -1008483263 -1003108240 -994223899 -980985167 -980107325 -965409045 -964780227 -957483248 -945834654 -944741150 -943568655 -941745183 -933705847 -933035789 -913206675 -912532095 -910716560 -891708798 -889489150 -879479411 -876899015 -868745827 -857968376 -855830631 -847398487 -839196168 -826612271 -823633339 -815899761 -811192543 -798870975 -798279241 -797114430 -736438571 -716087125 -715773696 -712997815 -712983291 -682002441 -675118713 -660827267 -636246171 -579569581 -577198896 -554735903 -552082539 -527201835 -514780119 -513520510 -498468403 -496196847 -477020195 -470939883 -463313648 -455734491 -447335427 -435019015 -433386095 -431939977 -424332979 -423890654 -416410341 -415841331 -412151651 -411513459 -401779575 -345636094 -339431207 -336972895 -327511477 -319314639 -298632863 -285007387 -284566019 -275480807 -246196702 -235597847 -223116863 -217763008 -216351803 -204345800 -196758399 -193297803 -188547518 -167647721 -165769656 -162532384 -148425929 -146431102 -141434315 -135135944 -119209887 -112395519 -111811039 -108333657 -98553121 -90618175 -86656399 -84033456 -77896355 -72006827 -46944862 -32194206 -27156414 -20656766 -8049323 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 23908491 24157817 25662096 30841243 34489129 38092160 38485749 39088169 54091296 57239589 63245986 67286597 70094349 102334155 112688866 116956384 126212877 135956833 140770274 153764121 165580141 171044845 174088025 192375533 199750121 207288144 217544849 217618722 225412217 233392493 267914296 277866872 297719717 299700119 305885837 307632137 319982248 322513954 363076002 368225352 375819880 385111345 406521634 407792008 425162338 428607904 433494437 439520866 445769703 447430277 476904098 477625087 479047640 484788320 485724693 510369096 511172301 512559680 519015297 519887010 523164546 537698139 538686495 572466946 575236290 596597538 615063885 626779336 650574555 653192827 663677033 668544240 676115649 679202349 680619202 695895453 696897233 701408733 708252800 732048309 764848393 788688354 791601474 793453837 797824181 809572578 814472144 822308361 844406421 858943736 863595449 871555938 878632002 885444751 887448560 946567201 962029693 968869026 972717154 972726019 976072482 982119865 983172896 1020930517 1021751743 1036105264 1071929805 1073992269 1075736893 1078443173 1082513827 1085121538 1091621922 1102226338 1122759743 1126134829 1134903170 1144438921 1149767586 1150043320 1151324569 1163854213 1177481423 1182303362 1183324359 1197517057 1203925421 1224874275 1231425347 1232204128 1250870283 1252772578 1260654389 1265227608 1270457195 1287498297 1297815145 1306058617 1306374013 1311674861 1330748738 1340547746 1367285497 1367387837 1371305377 1375036875 1390110773 1400843087 1407432322 1407736169 1412467027 1445263496 1476299253 1490993585 1495045709 1510415293 1526488431 1554160445 1582341984 1617528055 1626167272 1640636603 1642068909 1642909629 1697867392 1698174099 1711397512 1726311448 1750811945 1753804290 1766693207 1776683621 1796592009 1798021602 1798380843 1807838565 1818549533 1820529360 1836311903 1845853122 1867014871 1874176917 1886911151 1888312384 1911599776 1919601489 1927749315 1946118817 1950561807 1956813797 2004592773 2009306865 2029804546 2032742589 2048103889 2048113432 2056960834 2057847557 2080283312 2081405077 2087539970 2104519993 2118290601 2123398323 2131858402 2144908973 

'Quick' Sort:
-2144908973 -2131858402 -2123398323 -2118290601 -2104519993 -2087539970 -2081405077 -2080283312 -2057847557 -2056960834 -2048113432 -2048103889 -2032742589 -2029804546 -2009306865 -2004592773 -1956813797 -1950561807 -1946118817 -1927749315 -1919601489 -1911599776 -1888312384 -1886911151 -1874176917 -1867014871 -1845853122 -1836311903 -1820529360 -1818549533 -1807838565 -1798380843 -1798021602 -1796592009 -1776683621 -1766693207 -1753804290 -1750811945 -1726311448 -1711397512 -1698174099 -1697867392 -1642909629 -1642068909 -1640636603 -1626167272 -1617528055 -1582341984 -1554160445 -1526488431 -1510415293 -1495045709 -1490993585 -1476299253 -1445263496 -1412467027 -1407736169 -1407432322 -1400843087 -1390110773 -1375036875 -1371305377 -1367387837 -1367285497 -1340547746 -1330748738 -1311674861 -1306374013 -1306058617 -1297815145 -1287498297 -1270457195 -1265227608 -1260654389 -1252772578 -1250870283 -1232204128 -1231425347 -1224874275 -1203925421 -1197517057 -1183324359 -1182303362 -1177481423 -1163854213 -1151324569 -1150043320 -1149767586 -1144438921 -1134903170 -1126134829 -1122759743 -1102226338 -1091621922 -1085121538 -1082513827 -1078443173 -1075736893 -1073992269 -1071929805 -1036105264 -1021751743 -1020930517 -983172896 -982119865 -976072482 -972726019 -972717154 -968869026 -962029693 -946567201 -887448560 -885444751 -878632002 -871555938 -863595449 -858943736 -844406421 -822308361 -814472144 -809572578 -797824181 -793453837 -791601474 -788688354 -764848393 -732048309 -708252800 -701408733 -696897233 -695895453 -680619202 -679202349 -676115649 -668544240 -663677033 -653192827 -650574555 -626779336 -615063885 -596597538 -575236290 -572466946 -538686495 -537698139 -523164546 -519887010 -519015297 -512559680 -511172301 -510369096 -485724693 -484788320 -479047640 -477625087 -476904098 -447430277 -445769703 -439520866 -433494437 -428607904 -425162338 -407792008 -406521634 -385111345 -375819880 -368225352 -363076002 -322513954 -319982248 -307632137 -305885837 -299700119 -297719717 -277866872 -267914296 -233392493 -225412217 -217618722 -217544849 -207288144 -199750121 -192375533 -174088025 -171044845 -165580141 -153764121 -140770274 -135956833 -126212877 -116956384 -112688866 -102334155 -70094349 -67286597 -63245986 -57239589 -54091296 -39088169 -38485749 -38092160 -34489129 -30841243 -25662096 -24157817 -23908491 -14930352 -9227465 -5702887 -3524578 -2178309 -1346269 -832040 -514229 -317811 -196418 -121393 -75025 -46368 -28657 -17711 -10946 -6765 -4181 -2584 -1597 -987 -610 -377 -233 -144 -89 -55 -34 -21 -13 -8 -5 -3 -2 -1 -1 0 8049323 20656766 27156414 32194206 46944862 72006827 77896355 84033456 86656399 90618175 98553121 108333657 111811039 112395519 119209887 135135944 141434315 146431102 148425929 162532384 165769656 167647721 188547518 193297803 196758399 204345800 216351803 217763008 223116863 235597847 246196702 275480807 284566019 285007387 298632863 319314639 327511477 336972895 339431207 345636094 401779575 411513459 412151651 415841331 416410341 423890654 424332979 431939977 433386095 435019015 447335427 455734491 463313648 470939883 477020195 496196847 498468403 513520510 514780119 527201835 552082539 554735903 577198896 579569581 636246171 660827267 675118713 682002441 712983291 712997815 715773696 716087125 736438571 797114430 798279241 798870975 811192543 815899761 823633339 826612271 839196168 847398487 855830631 857968376 868745827 876899015 879479411 889489150 891708798 910716560 912532095 913206675 933035789 933705847 941745183 943568655 944741150 945834654 957483248 964780227 965409045 980107325 980985167 994223899 1003108240 1008483263 1014659279 1026133969 1026418105 1036647147 1044475943 1046575423 1055680967 1058612311 1060525039 1062385681 1070442683 1074470104 1078317847 1084667583 1088524075 1109290494 1109825406 1114639579 1128972440 1141377086 1144828775 1146314407 1176599134 1190560040 1194974568 1207821037 1209068504 1214555528 1215904419 1221724229 1225815811 1230842041 1232964055 1234788993 1242647099 1256657054 1259526462 1262539787 1264393720 1271569488 1280005790 1287770608 1289228135 1294114401 1302487535 1309912576 1317415307 1318891365 1323752223 1342539447 1344760007 1352116919 1358527051 1361106235 1376684011 1405925440 1408458269 1413538459 1418756969 1430963646 1446444701 1454097911 1458525411 1460087711 1464909729 1465773487 1477182014 1492918955 1501686169 1507123775 1517736479 1520513971 1538248318 1552179459 1559405063 1563375471 1571214277 1579382675 1581614984 1621802174 1627101779 1633875880 1652392144 1666785273 1674205151 1681088483 1681970654 1683903143 1686088699 1691007710 1696416131 1698104478 1709589543 1713023931 1717339191 1724637263 1725907855 1735022872 1741588030 1766226792 1770180926 1778728559 1781832971 1783728475 1787537663 1810161984 1827784403 1832819855 1837574691 1840171592 1842755184 1843752867 1869596475 1888440239 1920984255 1941116813 1946757903 1951048327 1956253592 1958435240 1960024281 1964504990 1973378861 1973608221 1973914317 1978344965 1988074275 1991649848 1998256175 2001070731 2015728079 2018789147 2021822589 2027310878 2031296807 2035081783 2046027531 2055058686 2057030967 2079590721 2080841703 2084912574 2085030416 2092787285 2094597475 2112826472 2114423111 2119115239 2133083224 2143601239 2144101118 

'Heap' Sort:
-2144908973 -2131858402 -2123398323 -2118290601 -2104519993 -2087539970 -2081405077 -2080283312 -2057847557 -2056960834 -2048113432 -2048103889 -2032742589 -2029804546 -2009306865 -2004592773 -1956813797 -1950561807 -1946118817 -1927749315 -1919601489 -1911599776 -1888312384 -1886911151 -1874176917 -1867014871 -1845853122 -1836311903 -1820529360 -1818549533 -1807838565 -1798380843 -1798021602 -1796592009 -1776683621 -1766693207 -1753804290 -1750811945 -1726311448 -1711397512 -1698174099 -1697867392 -1642909629 -1642068909 -1640636603 -1626167272 -1617528055 -1582341984 -1554160445 -1526488431 -1510415293 -1495045709 -1490993585 -1476299253 -1445263496 -1412467027 -1407736169 -1407432322 -1400843087 -1390110773 -1375036875 -1371305377 -1367387837 -1367285497 -1340547746 -1330748738 -1311674861 -1306374013 -1306058617 -1297815145 -1287498297 -1270457195 -1265227608 -1260654389 -1252772578 -1250870283 -1232204128 -1231425347 -1224874275 -1203925421 -1197517057 -1183324359 -1182303362 -1177481423 -1163854213 -1151324569 -1150043320 -1149767586 -1144438921 -1134903170 -1126134829 -1122759743 -1102226338 -1091621922 -1085121538 -1082513827 -1078443173 -1075736893 -1073992269 -1071929805 -1036105264 -1021751743 -1020930517 -983172896 -982119865 -976072482 -972726019 -972717154 -968869026 -962029693 -946567201 -887448560 -885444751 -878632002 -871555938 -863595449 -858943736 -844406421 -822308361 -814472144 -809572578 -797824181 -793453837 -791601474 -788688354 -764848393 -732048309 -708252800 -701408733 -696897233 -695895453 -680619202 -679202349 -676115649 -668544240 -663677033 -653192827 -650574555 -626779336 -615063885 -596597538 -575236290 -572466946 -538686495 -537698139 -523164546 -519887010 -519015297 -512559680 -511172301 -510369096 -485724693 -484788320 -479047640 -477625087 -476904098 -447430277 -445769703 -439520866 -433494437 -428607904 -425162338 -407792008 -406521634 -385111345 -375819880 -368225352 -363076002 -322513954 -319982248 -307632137 -305885837 -299700119 -297719717 -277866872 -267914296 -233392493 -225412217 -217618722 -217544849 -207288144 -199750121 -192375533 -174088025 -171044845 -165580141 -153764121 -140770274 -135956833 -126212877 -116956384 -112688866 -102334155 -70094349 -67286597 -63245986 -57239589 -54091296 -39088169 -38485749 -38092160 -34489129 -30841243 -25662096 -24157817 -23908491 -14930352 -9227465 -5702887 -3524578 -2178309 -1346269 -832040 -514229 -317811 -196418 -121393 -75025 -46368 -28657 -17711 -10946 -6765 -4181 -2584 -1597 -987 -610 -377 -233 -144 -89 -55 -34 -21 -13 -8 -5 -3 -2 -1 -1 0 8049323 20656766 27156414 32194206 46944862 72006827 77896355 84033456 86656399 90618175 98553121 108333657 111811039 112395519 119209887 135135944 141434315 146431102 148425929 162532384 165769656 167647721 188547518 193297803 196758399 204345800 216351803 217763008 223116863 235597847 246196702 275480807 284566019 285007387 298632863 319314639 327511477 336972895 339431207 345636094 401779575 411513459 412151651 415841331 416410341 423890654 424332979 431939977 433386095 435019015 447335427 455734491 463313648 470939883 477020195 496196847 498468403 513520510 514780119 527201835 552082539 554735903 577198896 579569581 636246171 660827267 675118713 682002441 712983291 712997815 715773696 716087125 736438571 797114430 798279241 798870975 811192543 815899761 823633339 826612271 839196168 847398487 855830631 857968376 868745827 876899015 879479411 889489150 891708798 910716560 912532095 913206675 933035789 933705847 941745183 943568655 944741150 945834654 957483248 964780227 965409045 980107325 980985167 994223899 1003108240 1008483263 1014659279 1026133969 1026418105 1036647147 1044475943 1046575423 1055680967 1058612311 1060525039 1062385681 1070442683 1074470104 1078317847 1084667583 1088524075 1109290494 1109825406 1114639579 1128972440 1141377086 1144828775 1146314407 1176599134 1190560040 1194974568 1207821037 1209068504 1214555528 1215904419 1221724229 1225815811 1230842041 1232964055 1234788993 1242647099 1256657054 1259526462 1262539787 1264393720 1271569488 1280005790 1287770608 1289228135 1294114401 1302487535 1309912576 1317415307 1318891365 1323752223 1342539447 1344760007 1352116919 1358527051 1361106235 1376684011 1405925440 1408458269 1413538459 1418756969 1430963646 1446444701 1454097911 1458525411 1460087711 1464909729 1465773487 1477182014 1492918955 1501686169 1507123775 1517736479 1520513971 1538248318 1552179459 1559405063 1563375471 1571214277 1579382675 1581614984 1621802174 1627101779 1633875880 1652392144 1666785273 1674205151 1681088483 1681970654 1683903143 1686088699 1691007710 1696416131 1698104478 1709589543 1713023931 1717339191 1724637263 1725907855 1735022872 1741588030 1766226792 1770180926 1778728559 1781832971 1783728475 1787537663 1810161984 1827784403 1832819855 1837574691 1840171592 1842755184 1843752867 1869596475 1888440239 1920984255 1941116813 1946757903 1951048327 1956253592 1958435240 1960024281 1964504990 1973378861 1973608221 1973914317 1978344965 1988074275 1991649848 1998256175 2001070731 2015728079 2018789147 2021822589 2027310878 2031296807 2035081783 2046027531 2055058686 2057030967 2079590721 2080841703 2084912574 2085030416 2092787285 2094597475 2112826472 2114423111 2119115239 2133083224 2143601239 2144101118 

Thrust Library 'Sort' algorithm:
-2144908973 -2131858402 -2123398323 -2118290601 -2104519993 -2087539970 -2081405077 -2080283312 -2057847557 -2056960834 -2048113432 -2048103889 -2032742589 -2029804546 -2009306865 -2004592773 -1956813797 -1950561807 -1946118817 -1927749315 -1919601489 -1911599776 -1888312384 -1886911151 -1874176917 -1867014871 -1845853122 -1836311903 -1820529360 -1818549533 -1807838565 -1798380843 -1798021602 -1796592009 -1776683621 -1766693207 -1753804290 -1750811945 -1726311448 -1711397512 -1698174099 -1697867392 -1642909629 -1642068909 -1640636603 -1626167272 -1617528055 -1582341984 -1554160445 -1526488431 -1510415293 -1495045709 -1490993585 -1476299253 -1445263496 -1412467027 -1407736169 -1407432322 -1400843087 -1390110773 -1375036875 -1371305377 -1367387837 -1367285497 -1340547746 -1330748738 -1311674861 -1306374013 -1306058617 -1297815145 -1287498297 -1270457195 -1265227608 -1260654389 -1252772578 -1250870283 -1232204128 -1231425347 -1224874275 -1203925421 -1197517057 -1183324359 -1182303362 -1177481423 -1163854213 -1151324569 -1150043320 -1149767586 -1144438921 -1134903170 -1126134829 -1122759743 -1102226338 -1091621922 -1085121538 -1082513827 -1078443173 -1075736893 -1073992269 -1071929805 -1036105264 -1021751743 -1020930517 -983172896 -982119865 -976072482 -972726019 -972717154 -968869026 -962029693 -946567201 -887448560 -885444751 -878632002 -871555938 -863595449 -858943736 -844406421 -822308361 -814472144 -809572578 -797824181 -793453837 -791601474 -788688354 -764848393 -732048309 -708252800 -701408733 -696897233 -695895453 -680619202 -679202349 -676115649 -668544240 -663677033 -653192827 -650574555 -626779336 -615063885 -596597538 -575236290 -572466946 -538686495 -537698139 -523164546 -519887010 -519015297 -512559680 -511172301 -510369096 -485724693 -484788320 -479047640 -477625087 -476904098 -447430277 -445769703 -439520866 -433494437 -428607904 -425162338 -407792008 -406521634 -385111345 -375819880 -368225352 -363076002 -322513954 -319982248 -307632137 -305885837 -299700119 -297719717 -277866872 -267914296 -233392493 -225412217 -217618722 -217544849 -207288144 -199750121 -192375533 -174088025 -171044845 -165580141 -153764121 -140770274 -135956833 -126212877 -116956384 -112688866 -102334155 -70094349 -67286597 -63245986 -57239589 -54091296 -39088169 -38485749 -38092160 -34489129 -30841243 -25662096 -24157817 -23908491 -14930352 -9227465 -5702887 -3524578 -2178309 -1346269 -832040 -514229 -317811 -196418 -121393 -75025 -46368 -28657 -17711 -10946 -6765 -4181 -2584 -1597 -987 -610 -377 -233 -144 -89 -55 -34 -21 -13 -8 -5 -3 -2 -1 -1 0 8049323 20656766 27156414 32194206 46944862 72006827 77896355 84033456 86656399 90618175 98553121 108333657 111811039 112395519 119209887 135135944 141434315 146431102 148425929 162532384 165769656 167647721 188547518 193297803 196758399 204345800 216351803 217763008 223116863 235597847 246196702 275480807 284566019 285007387 298632863 319314639 327511477 336972895 339431207 345636094 401779575 411513459 412151651 415841331 416410341 423890654 424332979 431939977 433386095 435019015 447335427 455734491 463313648 470939883 477020195 496196847 498468403 513520510 514780119 527201835 552082539 554735903 577198896 579569581 636246171 660827267 675118713 682002441 712983291 712997815 715773696 716087125 736438571 797114430 798279241 798870975 811192543 815899761 823633339 826612271 839196168 847398487 855830631 857968376 868745827 876899015 879479411 889489150 891708798 910716560 912532095 913206675 933035789 933705847 941745183 943568655 944741150 945834654 957483248 964780227 965409045 980107325 980985167 994223899 1003108240 1008483263 1014659279 1026133969 1026418105 1036647147 1044475943 1046575423 1055680967 1058612311 1060525039 1062385681 1070442683 1074470104 1078317847 1084667583 1088524075 1109290494 1109825406 1114639579 1128972440 1141377086 1144828775 1146314407 1176599134 1190560040 1194974568 1207821037 1209068504 1214555528 1215904419 1221724229 1225815811 1230842041 1232964055 1234788993 1242647099 1256657054 1259526462 1262539787 1264393720 1271569488 1280005790 1287770608 1289228135 1294114401 1302487535 1309912576 1317415307 1318891365 1323752223 1342539447 1344760007 1352116919 1358527051 1361106235 1376684011 1405925440 1408458269 1413538459 1418756969 1430963646 1446444701 1454097911 1458525411 1460087711 1464909729 1465773487 1477182014 1492918955 1501686169 1507123775 1517736479 1520513971 1538248318 1552179459 1559405063 1563375471 1571214277 1579382675 1581614984 1621802174 1627101779 1633875880 1652392144 1666785273 1674205151 1681088483 1681970654 1683903143 1686088699 1691007710 1696416131 1698104478 1709589543 1713023931 1717339191 1724637263 1725907855 1735022872 1741588030 1766226792 1770180926 1778728559 1781832971 1783728475 1787537663 1810161984 1827784403 1832819855 1837574691 1840171592 1842755184 1843752867 1869596475 1888440239 1920984255 1941116813 1946757903 1951048327 1956253592 1958435240 1960024281 1964504990 1973378861 1973608221 1973914317 1978344965 1988074275 1991649848 1998256175 2001070731 2015728079 2018789147 2021822589 2027310878 2031296807 2035081783 2046027531 2055058686 2057030967 2079590721 2080841703 2084912574 2085030416 2092787285 2094597475 2112826472 2114423111 2119115239 2133083224 2143601239 2144101118 

Thrust Library 'Transformation' sort algorithm:
-2144908973 -2131858402 -2123398323 -2118290601 -2104519993 -2087539970 -2081405077 -2080283312 -2057847557 -2056960834 -2048113432 -2048103889 -2032742589 -2029804546 -2009306865 -2004592773 -1956813797 -1950561807 -1946118817 -1927749315 -1919601489 -1911599776 -1888312384 -1886911151 -1874176917 -1867014871 -1845853122 -1836311903 -1820529360 -1818549533 -1807838565 -1798380843 -1798021602 -1796592009 -1776683621 -1766693207 -1753804290 -1750811945 -1726311448 -1711397512 -1698174099 -1697867392 -1642909629 -1642068909 -1640636603 -1626167272 -1617528055 -1582341984 -1554160445 -1526488431 -1510415293 -1495045709 -1490993585 -1476299253 -1445263496 -1412467027 -1407736169 -1407432322 -1400843087 -1390110773 -1375036875 -1371305377 -1367387837 -1367285497 -1340547746 -1330748738 -1311674861 -1306374013 -1306058617 -1297815145 -1287498297 -1270457195 -1265227608 -1260654389 -1252772578 -1250870283 -1232204128 -1231425347 -1224874275 -1203925421 -1197517057 -1183324359 -1182303362 -1177481423 -1163854213 -1151324569 -1150043320 -1149767586 -1144438921 -1134903170 -1126134829 -1122759743 -1102226338 -1091621922 -1085121538 -1082513827 -1078443173 -1075736893 -1073992269 -1071929805 -1036105264 -1021751743 -1020930517 -983172896 -982119865 -976072482 -972726019 -972717154 -968869026 -962029693 -946567201 -887448560 -885444751 -878632002 -871555938 -863595449 -858943736 -844406421 -822308361 -814472144 -809572578 -797824181 -793453837 -791601474 -788688354 -764848393 -732048309 -708252800 -701408733 -696897233 -695895453 -680619202 -679202349 -676115649 -668544240 -663677033 -653192827 -650574555 -626779336 -615063885 -596597538 -575236290 -572466946 -538686495 -537698139 -523164546 -519887010 -519015297 -512559680 -511172301 -510369096 -485724693 -484788320 -479047640 -477625087 -476904098 -447430277 -445769703 -439520866 -433494437 -428607904 -425162338 -407792008 -406521634 -385111345 -375819880 -368225352 -363076002 -322513954 -319982248 -307632137 -305885837 -299700119 -297719717 -277866872 -267914296 -233392493 -225412217 -217618722 -217544849 -207288144 -199750121 -192375533 -174088025 -171044845 -165580141 -153764121 -140770274 -135956833 -126212877 -116956384 -112688866 -102334155 -70094349 -67286597 -63245986 -57239589 -54091296 -39088169 -38485749 -38092160 -34489129 -30841243 -25662096 -24157817 -23908491 -14930352 -9227465 -5702887 -3524578 -2178309 -1346269 -832040 -514229 -317811 -196418 -121393 -75025 -46368 -28657 -17711 -10946 -6765 -4181 -2584 -1597 -987 -610 -377 -233 -144 -89 -55 -34 -21 -13 -8 -5 -3 -2 -1 -1 0 8049323 20656766 27156414 32194206 46944862 72006827 77896355 84033456 86656399 90618175 98553121 108333657 111811039 112395519 119209887 135135944 141434315 146431102 148425929 162532384 165769656 167647721 188547518 193297803 196758399 204345800 216351803 217763008 223116863 235597847 246196702 275480807 284566019 285007387 298632863 319314639 327511477 336972895 339431207 345636094 401779575 411513459 412151651 415841331 416410341 423890654 424332979 431939977 433386095 435019015 447335427 455734491 463313648 470939883 477020195 496196847 498468403 513520510 514780119 527201835 552082539 554735903 577198896 579569581 636246171 660827267 675118713 682002441 712983291 712997815 715773696 716087125 736438571 797114430 798279241 798870975 811192543 815899761 823633339 826612271 839196168 847398487 855830631 857968376 868745827 876899015 879479411 889489150 891708798 910716560 912532095 913206675 933035789 933705847 941745183 943568655 944741150 945834654 957483248 964780227 965409045 980107325 980985167 994223899 1003108240 1008483263 1014659279 1026133969 1026418105 1036647147 1044475943 1046575423 1055680967 1058612311 1060525039 1062385681 1070442683 1074470104 1078317847 1084667583 1088524075 1109290494 1109825406 1114639579 1128972440 1141377086 1144828775 1146314407 1176599134 1190560040 1194974568 1207821037 1209068504 1214555528 1215904419 1221724229 1225815811 1230842041 1232964055 1234788993 1242647099 1256657054 1259526462 1262539787 1264393720 1271569488 1280005790 1287770608 1289228135 1294114401 1302487535 1309912576 1317415307 1318891365 1323752223 1342539447 1344760007 1352116919 1358527051 1361106235 1376684011 1405925440 1408458269 1413538459 1418756969 1430963646 1446444701 1454097911 1458525411 1460087711 1464909729 1465773487 1477182014 1492918955 1501686169 1507123775 1517736479 1520513971 1538248318 1552179459 1559405063 1563375471 1571214277 1579382675 1581614984 1621802174 1627101779 1633875880 1652392144 1666785273 1674205151 1681088483 1681970654 1683903143 1686088699 1691007710 1696416131 1698104478 1709589543 1713023931 1717339191 1724637263 1725907855 1735022872 1741588030 1766226792 1770180926 1778728559 1781832971 1783728475 1787537663 1810161984 1827784403 1832819855 1837574691 1840171592 1842755184 1843752867 1869596475 1888440239 1920984255 1941116813 1946757903 1951048327 1956253592 1958435240 1960024281 1964504990 1973378861 1973608221 1973914317 1978344965 1988074275 1991649848 1998256175 2001070731 2015728079 2018789147 2021822589 2027310878 2031296807 2035081783 2046027531 2055058686 2057030967 2079590721 2080841703 2084912574 2085030416 2092787285 2094597475 2112826472 2114423111 2119115239 2133083224 2143601239 2144101118 

⏳📊 Runtime Results :

~ Manual Sorting Algorithms :
Bubble Sort Time: 16.328 ms
Quick Sort Time: 11.699 ms
Merge Sort Time: 1.070 ms
Heap Sort Time: 0.771 ms


~ Sorting by Thrust library : 
Thrust Sort Time: 0.081 ms

~Thrust Sorting Algorithm : 
Thrust Sort + Transformation Time: 0.033 ms

Worth noting is that manual sortings are run on the CPU while sorting algorithms by the Thrust library run on the GPU.

⚖️⏱️ Compare runtime Results :

I did the sortation for different values of N = [100, 1000, 10000, 100000]

🎓🏁 Conclusion

In Conclusion, when comparing manual sorting algorithms and sorting algorithms implemented using the Thrust library, the results show that the manual sorting algorithms (Bubble Sort, Quick Sort, Merge Sort, and Heap Sort) have significantly longer execution times, ranging from 0.771 ms to 16.328 ms.
On the other hand, the sorting algorithm provided by the Thrust library demonstrates significantly improved performance, with a sorting time of only 0.081 ms.
Additionally, when applying a transformation step before sorting using the Thrust library, the total execution time is further reduced to an impressive 0.033 ms.
These results highlight the efficiency and effectiveness of leveraging GPU acceleration through the Thrust library for sorting operations, offering substantial performance gains compared to traditional CPU-based manual sorting algorithms.

In collaboration with STEFANO ACIERNO