I have a question where we need to sort only the even indices of an array using divide and conquer.
What I tried was modifying the original mergeSort
function such that it will sort the even elements of subarrays. But in the merge sort function, we won't get every single element as we wouldn't know where to place if we get a single element, thus I made it so that base cases are when the subarray is of size 3 or 4. it will sort the subarray, but in a way that the even index in term of even index of main array only is sorted, thus line x.
The result I got was that the odd elements were untouched, but the even elements were not sorted correctly.
below is my code:
#include <stdio.h>
void merge(int arr[], int l, int m, int r);
void mergeSort(int arr[], int si, int ei);
int main() {
int num;
scanf("%d", &num);
int arr[num];
for (int i = 0; i < num; i++) {
scanf("%d", &arr[i]);
}
mergeSort(arr, 0, num - 1);
for (int i = 0; i < num; i++) {
printf("%d ", arr[i]);
}
return 0;
}
void mergeSort(int arr[], int si, int ei) {
if ((ei - si == 2) && (si % 2 == 0)) {
if (arr[si] > arr[si + 2]) {
int temp = arr[si];
arr[si] = arr[si + 2];
arr[si + 2] = arr[si];
}
} //base case 1
if ((ei - si == 3)) {
int x = (si % 2 == 0) ? si : si + 1; //line x
if (arr[x] > arr[x + 2]) {
int temp = arr[x];
arr[x] = arr[x + 2];
arr[x + 2] = arr[x];
} //base case 2
}
if (si < ei) {
int mid = si + (ei - si) / 2;
mergeSort(arr, si, mid); //calling merge sort on both the halves of array
mergeSort(arr, mid + 1, ei);
merge(arr, si, mid, ei);
}
}
void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int arr1[n1], arr2[n2];
for (i = 0; i < n1; i++)
arr1[i] = arr[l + i];
for (j = 0; j < n2; j++)
arr2[j] = arr[m + 1 + j];
for (int i = 0; i < n1; i = i + 2) {
arr[i] = arr1[i];
}
i = (n1 % 2 == 0) ? 0 : 1;
for (;i < n2; i = i + 2) {
arr[i+n1] = arr2[i];
}
i = 0;
j = (n1 % 2 == 0) ? 0 : 1, k = l;
while (i < n1) {
arr[k] = arr1[i];
k = k + 2;
i = i + 2;
}
while (j < n2) {
arr[k++] = arr2[j];
k = k + 2;
j = j + 2;
}
while (i < n1) {
arr[k] = arr1[i];
k = k + 2;
i = i + 2;
}
while (j < n2) {
arr[k] = arr2[j];
k = k + 2;
j = j + 2;
}
}