-
Notifications
You must be signed in to change notification settings - Fork 6
/
Merge_Sort.cpp
109 lines (95 loc) · 1.86 KB
/
Merge_Sort.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <bits/stdc++.h>
using namespace std;
class node
{
public:
int data;
node *next;
node(int x)
{
data = x;
next = 0;
};
node(int n, node *add)
{
data = n;
next = add;
}
};
void print(node *p)
{
while (p)
{
cout << p->data << " ";
p = p->next;
}
}
node *merge(node *first, node *second)
{
node *NewHead, *last;
if (first->data < second->data)
{
last = NewHead = first;
first = first->next;
last->next = 0;
}
else
{
last = NewHead = second;
second = second->next;
last->next = 0;
}
while (first && second)
{
if (first->data < second->data)
{
last->next = first;
last = first;
first = first->next;
last->next = 0;
}
else
{
last->next = second;
last = second;
second = second->next;
last->next = 0;
}
}
if (first)
{
last->next = first;
}
else if (second)
{
last->next = second;
}
return NewHead;
}
node *sortList(node *head)
{
// Base Case if the list has 0 or 1 element it means it is already sorted
if (!head || !head->next)
return head;
node *slow = head;
node *fast = head->next;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
// Divide the list into two parts (one start with head and other with fast)
fast = slow->next;
slow->next = NULL;
// Merge these List
return merge(sortList(head), sortList(fast));
}
int main()
{
node *head1 = new node(5, 0);
node *head2 = new node(0, head1);
node *head3 = new node(9, head2);
node *head4 = new node(1, head3);
node *hed = sortList(head4);
print(hed);
}