Cracking The Coding Interview/Q 11.1

From Software Engineers Wiki
Jump to: navigation, search

You are given two sorted arrays, A and B, where A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order.

Answer

#include <iostream>
#include <array>

int main(void)
{
        std::array<int, 16> arr_a {{ 1, 11, 21, 31, 41, 51, 61, 71, 81, 91, 101 }};
        std::array<int, 16> arr_b {{ 0, 15, 45, 47, 85, 155 }};

        /* merge */
        {
                int *data_a = arr_a.data();
                int *data_b = arr_b.data();
                int *data_ins;
                int elem_a = 10, elem_b = 6;

                data_ins = data_a + elem_a + elem_b - 1;
                data_a += elem_a - 1;
                data_b += elem_b - 1;

                while (elem_b != 0) {
                        if (data_a && (*data_a > *data_b)) {
                                *data_ins = *data_a--;
                                if (--elem_a == 0)
                                        data_a = NULL;
                        } else {
                                *data_ins = *data_b--;
                                --elem_b;
                        }
                        --data_ins;
                }
        }

        /* print */
        {
                std::array<int, 16>::iterator it;
                int elem = 16;

                for (it = arr_a.begin(); it != arr_a.end() && elem > 0; ++it, --elem)
                        std::cout << *it << " ";

                std::cout << std::endl;
        }

        return 0;
}

Results:

0 1 11 15 21 31 41 45 47 51 61 71 81 85 91 155 
Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox