Skip to content

Instantly share code, notes, and snippets.

@sriharshachilakapati
Created February 7, 2020 08:12
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save sriharshachilakapati/e57f68cf819ae031cf323b89764cc2ff to your computer and use it in GitHub Desktop.
Save sriharshachilakapati/e57f68cf819ae031cf323b89764cc2ff to your computer and use it in GitHub Desktop.
Sort 3 different arrays into 1 array
#include <stdio.h>
#include <stdlib.h>
void merge_sort(int*, int*, int);
void merge2(int* dest, int* a, int* b, int lenA, int lenB) {
// Array indices
int dI = 0, aI = 0, bI = 0;
// Copy the values from all the arrays
while (aI < lenA && bI < lenB) {
if (a[aI] <= b[bI]) {
dest[dI++] = a[aI++];
} else {
dest[dI++] = b[bI++];
}
}
// Copy all the rest of a
while (aI < lenA) {
dest[dI++] = a[aI++];
}
// Copy all the rest of b
while (bI < lenB) {
dest[dI++] = b[bI++];
}
}
void merge3(int* dest, int* a, int* b, int* c, int lenA, int lenB, int lenC) {
// Array indices
int dI = 0, aI = 0, bI = 0, cI = 0;
// Copy the values from all the arrays
while (aI < lenA && bI < lenB && cI < lenC) {
if (a[aI] <= b[bI]) {
if (a[aI] <= c[cI]) {
dest[dI++] = a[aI++];
} else {
dest[dI++] = c[cI++];
}
} else {
if (b[bI] <= c[cI]) {
dest[dI++] = b[bI++];
} else {
dest[dI++] = c[cI++];
}
}
}
// After running the above loop, one of the array will be completely merged.
// Time to merge the remaining 2 arrays.
if (aI == lenA) {
merge2(dest + dI, b + bI, c + cI, lenB - bI, lenC - cI);
} else if (bI == lenB) {
merge2(dest + dI, a + aI, c + cI, lenA - aI, lenC - cI);
} else {
merge2(dest + dI, a + aI, b + bI, lenA - aI, lenB - bI);
}
}
void merge_sort3(int* dest, int* a, int* b, int* c, int lenA, int lenB, int lenC) {
// Create a temporary destination
int result[lenA + lenB + lenC];
// Recursively sort using 2-way merge sort
merge_sort(result, a, lenA);
merge_sort(result + lenA, b, lenB);
merge_sort(result + lenA + lenB, c, lenC);
// Merge them finally
merge3(dest, result, result + lenA, result + lenA + lenB, lenA, lenB, lenC);
}
void merge_sort(int* dest, int* a, int len) {
// No need to sort if the sub length is 1
if (len < 2) {
*dest = *a;
return;
}
// Create a temporary destination
int result[len];
// Find the mid point
int mid = len / 2;
// Do the sorting
merge_sort(result, a, mid);
merge_sort(result + mid, a + mid, len - mid);
// Merge back
merge2(dest, result, result + mid, mid, len - mid);
}
int main() {
int a[4] = { 5, 3, 2, 11 };
int b[6] = { 2, -1, 23, 34, 4, 5 };
int c[1] = { 4 };
int d[11] = {};
merge_sort3(d, a, b, c, 4, 6, 1);
for (int i = 0; i < 11; i++) {
printf("%d ", d[i]);
}
printf("\n");
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment