## C++ 之“合并排序”代码

```#include <iostream>
#include <time.h>
#include <stdlib.h>
#define N 1000000
using namespace std;

struct node
{
int data;
node *next;
};

{
node *tmp = new node;
tmp->data = data;
return tmp;
}

{
{
delete tmp;
}
}

{
{
}
}

node *mix(node *left, node *right)
{
node *result = NULL;
while((left!=NULL)&&(right!=NULL))
{
if(left->data < right->data)
{
result = insert(result, left->data);
left = remove(left);
}
else
{
result = insert(result, right->data);
right = remove(right);
}
}
while(left!=NULL)
{
result = insert(result, left->data);
left = remove(left);
}
while(right!=NULL)
{
result = insert(result,right->data);
right = remove(right);
}
result = reverse(result);
return result;
}

{
if(n==1)
// divide into 2 lists
for(int i=0;i<n/2-1;i++)
right = right->next;
node *tmp = right;
right = right->next;
tmp->next = NULL;
// do merge sort on both lists
left = merge(left,n/2);
right = merge(right,n-n/2);
// mix left and right
return mix(left,right);
}

int main()
{
clock_t start,end;
double diff;
srand ( (unsigned int)time(NULL) );
for(int i=0;i<N;i++)

start = clock();
end = clock();
diff = end - start;
cout << "Merge sort for linked list: " << diff/CLOCKS_PER_SEC << " seconds..." << endl;

//{
// cout << head->data << endl;
//}

return 0;
}```