fork download
copy 
  1. #include <iostream>
  2. #include <cstdlib>
  3.  
  4. using namespace std;
  5.  
  6. struct node {
  7.   int data;
  8.   struct node *next;
  9.  
  10. };
  11.  
  12. void traverse(struct node *head)
  13. {
  14.     while ( head != NULL ){
  15.          cout << head->data << endl;
  16.          head = head->next;
  17.       }
  18. }
  19.  
  20.  
  21. void insert ( struct node **head, int num)
  22. {
  23.       struct node *temp = (struct node*) malloc(sizeof(struct node));
  24.       temp->data = num;
  25.       temp->next = NULL;
  26.      if ( *head == NULL ){
  27.           *head = temp;
  28.           return;
  29.      }
  30.      temp->next = *head;
  31.      *head = temp;
  32.  
  33. }
  34.  
  35. void merge( struct node **head ,struct node *b)
  36. {
  37.     struct node dummy;
  38.     struct node *a = *head;
  39.     struct node *result = &dummy;
  40.     dummy.next = NULL;
  41.  
  42.     while (1)
  43.     {
  44.          if ( a == NULL && b == NULL) {
  45.             break;
  46.          }
  47.          if (  a == NULL ){
  48.             result->next = b;
  49.             break;
  50.          }
  51.          if ( b == NULL ){
  52.             result->next = a;
  53.             break;
  54.          }
  55.          if ( a->data < b->data){
  56.  
  57.               result->next = a;
  58.               a = a->next;
  59.               result = result->next;
  60.               result->next = NULL;
  61.          }
  62.          else {
  63.                 result->next = b;
  64.                b = b->next;
  65.               result = result->next;
  66.               result->next = NULL;
  67.  
  68.          }
  69.  
  70.  
  71.  
  72.  
  73.     }
  74.  
  75.     *head = dummy.next;
  76.  
  77. }
  78.  
  79. void merge_sort( struct node **head, int n)
  80. {
  81.  
  82.       if ( *head ==NULL || (*head)->next == NULL ){
  83.           return;
  84.       }
  85.  
  86.       int count = 0;
  87.       struct node *temp = *head;
  88.       int mid = n/2;
  89.       struct node *p;
  90.       while (temp != NULL && count < mid ) {
  91.            p = temp;
  92.            temp = temp->next;
  93.            count++;
  94.       }
  95.       p->next = NULL;
  96.       merge_sort(head,mid);
  97.       merge_sort(&temp,n-mid);
  98.  
  99.       merge(head,temp);
  100.  
  101.  
  102. }
  103.  
  104. int main()
  105. {
  106.      struct node *head = NULL;
  107.  
  108.      int n;
  109.      cin >> n;
  110.  
  111.      for ( int i = 0; i < n; i++ ){
  112.         int x;
  113.         cin >> x;
  114.         insert(&head,x);
  115.      }
  116.  
  117.  
  118.      merge_sort(&head,n);
  119.      traverse(head);
  120.  
  121. }
  122.  
  123.  
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
6
5 4 3 2 1 9
stdout
copy 
1
2
3
4
5
9
https://ideone.com/eYfGWE
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!