fork download
copy 
  1. uses math;
  2. type lg=longint;
  3. 	m1c=array[0..500000] of lg;
  4. const run=1;
  5. var a:m1c;
  6. 	i,n,m:lg;
  7. procedure insertionsort(var a:m1c;l,r:lg);
  8. var i,j,tmp:lg;
  9. begin
  10. 	for i:=l+1 to r do
  11. 		begin
  12. 			j:=i-1; tmp:=a[i];
  13. 			while (j>=l) and (a[j]>tmp) do
  14. 				begin
  15. 					a[j+1]:=a[j]; dec(j);
  16. 				end;
  17. 			a[j+1]:=tmp;
  18. 		end;
  19. end;
  20. procedure merge(var a:m1c;l,m,r:lg);
  21. var i,j,k:lg;
  22. 	left,right:m1c;
  23. begin
  24. 	for i:= l to m do
  25. 		left[i-l]:=a[i];
  26. 	for i:=m+1 to r do
  27. 		right[i-m-1]:=a[i];
  28. 	i:=0; j:=i; k:=l;
  29. 	while (i<m-l+1) and (j<r-m) do
  30. 		begin
  31. 			if (left[i]<right[j]) then
  32. 				begin
  33. 					a[k]:=left[i]; inc(i); inc(k);
  34. 				end
  35. 			else
  36. 				begin
  37. 					a[k]:=right[j]; inc(j); inc(k);
  38. 				end;
  39. 		end;
  40. 	while (i<m-l+1) do
  41. 		begin
  42. 			a[k]:=left[i]; inc(i); inc(k);
  43. 		end;
  44. 	while (j<r-m) do
  45. 		begin
  46. 			a[k]:=right[j]; inc(j); inc(k);
  47. 		end;	
  48. end;
  49. procedure pigsort(var a:m1c; n:lg);
  50. var l,m,r,i,tmp:lg;
  51. begin
  52. 	i:=0;
  53. 	while (i<n) do
  54. 		begin
  55. 			insertionsort(a,i,min(i+run-1,n-1)); i:=i+run;
  56. 		end;
  57. 	tmp:=run;
  58. 	while (tmp<n) do
  59. 		begin
  60. 			l:=0;
  61. 			while (l<n) do
  62. 				begin
  63. 					r:=min(l+(tmp shl 1)-1,n-1); m:= l + tmp-1;
  64. 					merge(a,l,m,r);
  65. 					l:=l+(tmp shl 1);
  66. 				end;
  67. 			tmp:=tmp shl 1;
  68. 		end;
  69. end;
  70. begin	
  71. 	readln(n,m);
  72. 	for i:= 0 to n-1 do
  73. 		read(a[i]);
  74. 	if (n<=run) then insertionsort(a,0,n-1) else pigsort(a,n);
  75. 	for i:= 0 to n-1 do
  76. 		write(a[i],' ');
  77. end.
Success #stdin #stdout 0s 5520KB
comments (?)
stdin
copy 
5 7
5 2 1 6 7
stdout
copy 
1 2 5 6 7
https://ideone.com/hx00s3
language:
Pascal (fpc 3.0.4)
created:
1 year 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!