1 /* This code is part of the tng compression routines.
3 * Written by Daniel Spangberg
4 * Copyright (c) 2010, 2013, The GROMACS development team.
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of the Revised BSD License.
15 #include "../../include/compression/warnmalloc.h"
16 #include "../../include/compression/merge_sort.h"
18 static void ms_inner(void *base, size_t size,
19 size_t start, size_t end,
20 int (*compar)(const void *v1,const void *v2,const void *private),
27 char *cbase=(char *)base;
28 middle=start+(end-start)/2;
30 printf("For start %d end %d obtained new middle: %d\n",start,end,middle);
34 compar,private,workarray);
37 compar,private,workarray);
39 printf("For start %d end %d Before merge: Comparing element %d with %d\n",start,end,middle-1,middle);
41 if (compar(cbase+(middle-1)*size,cbase+middle*size,private)>0)
43 /* Merge to work array. */
44 size_t i, n=end-start;
51 memcpy(workarray+i*size,cbase+iright*size,size);
56 memcpy(workarray+i*size,cbase+ileft*size,size);
62 printf("For start %d end %d In merge: Comparing element %d with %d\n",start,end,ileft,iright);
64 if (compar(cbase+ileft*size,cbase+iright*size,private)>0)
66 memcpy(workarray+i*size,cbase+iright*size,size);
71 memcpy(workarray+i*size,cbase+ileft*size,size);
76 /* Copy result back. */
77 memcpy(cbase+start*size,workarray,(end-start)*size);
83 void Ptngc_merge_sort(void *base, size_t nmemb, size_t size,
84 int (*compar)(const void *v1,const void *v2,const void *private),
87 char *warr=warnmalloc(nmemb*size);
88 ms_inner(base,size,0,nmemb,compar,private,warr);
95 static int compint(const void *v1, const void *v2,const void *private)
97 const int *i1=(const int *)v1;
98 const int *i2=(const int *)v2;
107 static int qcompint(const void *v1, const void *v2)
109 return compint(v1,v2,NULL);
115 int *arr=warnmalloc(N*sizeof *arr);
120 merge_sort(arr,N,sizeof *arr,compint,NULL);
122 qsort(arr,N,sizeof *arr,qcompint);
125 printf("%d %d\n",i,arr[i]);