Here is source code of the C++ Program to demonstrate the implementation of Merge Sort using Linked.

USA Ussays > Uncategorized > Here is source code of the C++ Program to demonstrate the implementation of Merge Sort using Linked.

Here is source code of the C++ Program to demonstrate the implementation of Merge Sort using Linked.

Here is source code of the C++ Program to demonstrate the implementation of Merge Sort using Linked List. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2. * C++ Program to Implement Merge Sort using Linked List
  3. */
  4. #include
  5. #include
  6. #include
  7. using namespace std;
  8. /*
  9. * Node Declaration
  10. */
  11. struct node
  12. {
  13. int data;
  14. struct node* next;
  15. };
  18. struct node* SortedMerge(node* a, node* b);
  19. void FrontBackSplit(node* source, node** frontRef, node** backRef);
  21. /* sorts the linked list by changing next pointers (not data) */
  22. void MergeSort(struct node** headRef)
  23. {
  24. node* head = *headRef;
  25. node* a;
  26. node* b;
  27. if ((head == NULL) || (head->next == NULL))
  28. {
  29. return;
  30. }
  31. FrontBackSplit(head, &a, &b);
  32. MergeSort(&a);
  33. MergeSort(&b);
  34. *headRef = SortedMerge(a, b);
  35. }
  36. /* merge the sorted linked lists */
  37. node* SortedMerge(struct node* a, struct node* b)
  38. {
  39. node* result = NULL;
  40. if (a == NULL)
  41. return b;
  42. else if (b==NULL)
  43. return a;
  44. if (a->data <= b->data)
  45. {
  46. result = a;
  47. result->next = SortedMerge(a->next, b);
  48. }
  49. else
  50. {
  51. result = b;
  52. result->next = SortedMerge(a, b->next);
  53. }
  54. return result;
  55. }
  57. /* Split the nodes of the given list into front and back halves*/
  58. void FrontBackSplit(node* source, node** frontRef, node** backRef)
  59. {
  60. node* fast;
  61. node* slow;
  62. if (source==NULL || source->next==NULL)
  63. {
  64. *frontRef = source;
  65. *backRef = NULL;
  66. }
  67. else
  68. {
  69. slow = source;
  70. fast = source->next;
  71. while (fast != NULL)
  72. {
  73. fast = fast->next;
  74. if (fast != NULL)
  75. {
  76. slow = slow->next;
  77. fast = fast->next;
  78. }
  79. }
  80. *frontRef = source;
  81. *backRef = slow->next;
  82. slow->next = NULL;
  83. }
  84. }
  86. /* print nodes in a given linked list */
  87. void printList(node *node)
  88. {
  89. while (node != NULL)
  90. {
  91. coutdata
  92. node = node->next;
  93. }
  94. }
  96. /* insert a node at the beginging of the linked list */
  97. void push(node** head_ref, int new_data)
  98. {
  99. node *new_node = new node;
  100. new_node->data = new_data;
  101. new_node->next = (*head_ref);
  102. (*head_ref) = new_node;
  103. }
  104. /* Main */
  105. int main()
  106. {
  107. node* res = NULL;
  108. node* a = NULL;
  109. push(&a, 15);
  110. push(&a, 10);
  111. push(&a, 5);
  112. push(&a, 20);
  113. push(&a, 3);
  114. push(&a, 2);
  115. MergeSort(&a);
  116. cout
  117. printList(a);
  118. return 0;
  119. }