fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. void merge (int X[],int bt1,int w1,int bt2,int w2, int Z[]) {
  4. 	int i=bt1, j=bt2, bp1=bt1+w1-1, bp2=bt2+w2-1, k=bt1;
  5. 	while (i<=bp1 && j<=bp2) {
  6. 		if (X[i]<X[j]){
  7. 			Z[k] = X[i];
  8. 			i++; k++;
  9. 		}
  10. 		else {
  11. 			Z[k] = X[j];
  12. 			j++; k++;
  13. 		}
  14. 	}
  15. 	while (i<=bp1) {
  16. 		Z[k] = X[i];
  17. 		i++; k++;
  18. 	}
  19. 	while (j<=bp2) {
  20. 		Z[k] = X[j];
  21. 		j++; k++; 
  22. 	}
  23. }
  24. void mergePass(int X[],int n,int K,int Z[]){
  25. 	int cv = n/(2*K); 
  26. 	int s = 2*K*cv;
  27. 	int r = n-s;
  28. 	for (int j=1; j<=cv; j++){
  29. 		int b1 = (2*j -2)*K;
  30. 		merge(X, b1, K, b1+K, K, Z);
  31. 	}
  32. 	if (r<=K)
  33. 		for (int j=0; j<r; j++)
  34. 			Z[s+j] = X[s+j];
  35. 	else
  36. 		merge(X, s,K, s+K, r-K, Z);
  37. }
  38. void mergeSort (int X[],int n)
  39. {
  40. 	int K = 1;
  41. 	int *Z = new int[n]();
  42. 	while (K < n)
  43. 	{
  44. 		mergePass(X, n, K, Z);
  45. 		mergePass(Z, n, 2*K, X);
  46. 		K = K*4;
  47. 	}
  48. }
  49. void createNumber(int A[], int n)
  50. {
  51. 	srand((int)time(0));
  52. 	for (int i = 0; i < n; ++i)
  53. 	{
  54. 		A[i] = -10000 + rand() %(10000- (-10000) + 1);
  55. 	}
  56. }
  57. void show(int A[], int n)
  58. {
  59. 	for (int i = 0; i < n; ++i)
  60. 	{
  61. 		cout<<A[i]<<" ";
  62. 	}
  63. }
  64. int main(int argc, char const *argv[])
  65. {
  66. 	int n = 10;
  67. 	int *A = new int[n];
  68. 	createNumber(A,n);
  69. 	show(A,n);
  70. 	cout<<endl;
  71. 	mergeSort(A,n);
  72. 	show(A,n);
  73. 	return 0;
  74. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-4358 9352 -469 -3808 1880 4288 9182 5004 -3451 -7859 
-7859 -4358 -3808 -3451 -469 1880 4288 5004 9182 9352
https://ideone.com/6Ap2Qo
language:
C++ (gcc 8.3)
created:
1 day 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!