#include <iostream>
using namespace std;
class merge {
public:
// Batcher's sort function for subarray starting from lo with N elements
int *batchersSort(int a[], int lo, int N) {
int *s; // pointer to the sorted subarray
if (N > 1) { // if the subarray has more than one element
int mid = N / 2; // divide the subarray into two halves
int m = mid; // number of elements in the left half
int n = N - mid; // number of elements in the right half
int *u = new int[m]; // allocate memory for the left half
int *v = new int[n]; // allocate memory for the right half
u = batchersSort(a, lo, m); // recursively sort the left half
v = batchersSort(a, lo + mid, n); // recursively sort the right half
s = batcher(u, v, m, n); // merge the sorted halves
delete[] u; // deallocate memory for the left half
delete[] v; // deallocate memory for the right half
return s; // return the pointer to the merged and sorted subarray
}
else { // if the subarray has only one element
s = new int; // allocate memory for the subarray
s[0] = a[lo]; // set the element to the subarray
return s; // return the pointer to the subarray
}
}
// Function to compare and interchange two integers
void compareInterchange(int &x, int &y) {
int temp;
if (x > y) {
temp = x;
x = y;
y = temp;
}
}
// Function to merge two sorted subarrays u and v of sizes m and n respectively
int *batcher(int u[], int v[], int m, int n) {
int i, j, *s; // pointers for the subarrays and the merged subarray
if (m == 0) { // if the left subarray is empty
s = new int; // allocate memory for the merged subarray
s[0] = v[0]; // set the first element of the right subarray to the merged subarray
return s; // return the pointer to the merged subarray
}
else if (n == 0) { // if the right subarray is empty
s[0] = u[0]; // set the first element of the left subarray to the merged subarray
return s; // return the pointer to the merged subarray
}
else if (m == 1 && n == 1) { // if both subarrays have only one element
compareInterchange(u[0], v[0]); // compare and interchange the elements if necessary
s = new int[2]; // allocate memory for the merged subarray
s[0] = u[0]; // set the first element of the left subarray to the merged subarray
s[1] = v[0]; // set the second element of the right subarray to the merged subarray
return s; // return the pointer to the merged subarray
}
else {
int x, y; // pointers for the middle elements of the subarrays
if (m % 2 == 1) { // if the number of elements in the left subarray is odd
x = m / 2 + 1; // set the middle element to the second half of the left subarray
}
else {
x = m / 2; // set the middle element to the first half of the left subarray
}
if (n % 2 == 1) { // if the number of elements in the right subarray is odd
y = n / 2 + 1; // set the middle element to the second half of the right subarray
}
else {
y = n / 2; // set the middle element to the first half of the right subarray
}
int *ou = new int[x]; // allocate memory for the first half of the left subarray
int *ov = new int[y]; // allocate memory for the first half of the right subarray
for (i = 0, j = 0; i < m; i += 2, ++j) { // copy the elements from the left subarray to the first half
ou[j] = u[i];
}
for (i = 0, j = 0; i < n; i += 2, ++j) { // copy the elements from the right subarray to the first half
ov[j] = v[i];
}
int *a = batcher(ou, ov, x, y); // merge the first halves of the subarrays
delete[] ou; // deallocate memory for the first half of the left subarray
delete[] ov; // deallocate memory for the first half of the right subarray
int *eu = new int[m / 2]; // allocate memory for the second half of the left subarray
int *ev = new int[n / 2]; // allocate memory for the second half of the right subarray
for (i = 1, j = 0; i < m; i += 2, ++j) { // copy the elements from the left subarray to the second half
eu[j] = u[i];
}
for (i = 1, j = 0; i < n; i += 2, ++j) { // copy the elements from the right subarray to the second half
ev[j] = v[i];
}
int *b = batcher(eu, ev, m / 2, n / 2); // merge the second halves of the subarrays
delete[] eu; // deallocate memory for the second half of the left subarray
delete[] ev; // deallocate memory for the second half of the right subarray
int c; // variable to determine the number of elements to be merged from the second halves
if ((m % 2 == 0) && (n % 2 == 0)) {
c = m / 2 + n / 2 - 1; // if both subarrays have an even number of elements
}
else {
c = m / 2 + n / 2; // if one or both subarrays have an odd number of elements
}
for (i = 1; i <= c; i++) { // merge the sorted subarrays
compareInterchange(b[i - 1], a[i]); // compare and interchange the elements if necessary
s = new int[m + n]; // allocate memory for the merged subarray
s[0] = a[0]; // set the first element of the left subarray to the merged subarray
}
for (i = 1, j = 1; i <= c; ++i) { // merge the sorted subarrays
s[j++] = b[i - 1]; // set the elements of the right subarray to the merged subarray
s[j++] = a[i]; // set the elements of the left subarray to the merged subarray
}
if (m % 2 == 0 && n % 2 == 0) {
s[j++] = b[m / 2 + n / 2 - 1]; // if both subarrays have an even number of elements, set the middle element of the merged subarray
}
else if (m % 2 == 1 && n % 2 == 1) {
s[j++] = a[m / 2 + n / 2 + 1]; // if both subarrays have an odd number of elements, set the middle element of the merged subarray
}
delete[] a; // deallocate memory for the first half of the merged subarray
delete[] b; // deallocate memory for the second half of the merged subarray
return s; // return the pointer to the merged and sorted subarray
}
}
};
int main()
{
merge ob;
int n;
cout << "Enter The Number Of Elements In The Array: " << endl;
cin >> n;
int a[n];
cout << "Enter The " << n << " Elements Of The Array: " << endl;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
int *p = ob.batchersSort(a, 0, n);
for (int i = 0; i < n; i++)
{
cout << p[i] << " ";
}
return 0;
}
Comments
Post a Comment