Recursive Merge Sort in C++

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <ctime>

#define ARR_SIZE 15

using namespace std;

void print(vector<int> &vt)
{
    copy(vt.begin(), vt.end(), ostream_iterator<int>(cout, "  "));
    cout<<endl;
}

void merge(vector<int> &vt, int p, int r)
{
    int mid = floor((p+r)/2);
    int i1 = 0;
    int i2 = p;
    int i3 = mid + 1;

    vector<int> t_vt;
    t_vt.reserve(r-p+1);

    while( i2 <= mid && i3 <= r)
    {
        if ( vt[i2] < vt[i3] )
            t_vt[i1++] = vt[i2++];
        else
            t_vt[i1++] = vt[i3++];
    }

    while (i2 <= mid )
        t_vt[i1++] = vt[i2++];

    while ( i3 <= r )
        t_vt[i1++] = vt[i3++];

    for(int i = p; i <= r; i++)
        vt[i] = t_vt[i-p];

}

/*Algorithm
    1> Split the list into two equal parts at the middle
    2> Apply merge_sort() on each list
    3> Merge both the lists
*/
void merge_sort(vector<int> &vt, int p, int r)
{
    if(p<r)
    {
        int mid = floor((p+r)/2);
        merge_sort(vt, p, mid);
        merge_sort(vt, mid+1, r);
        merge(vt, p, r);
    }
}

int main()
{
    vector<int> vt;
    vt.reserve(ARR_SIZE);

    srand(time(NULL));

    for(int i=0; i<ARR_SIZE; i++)
        vt.push_back(rand()%1000);

    cout<<"Unsorted : "<<endl;
    print(vt);

    merge_sort(vt, 0, vt.size()-1);

    cout<<"Sorted : "<<endl;
    print(vt);

    return 0;
}

Output :-

Unsorted :
308  259  354  738  444  7  891  756  63  56  460  961  732  38  648
Sorted :
7  38  56  63  259  308  354  444  460  648  732  738  756  891  961

Union and Intersection of two Linked Lists in C++

#include <iostream>

using namespace std;

class LinkedList
{
    //Linked List Node
    struct node
    {
        int data;
        node *next;
    };

    //Header Node that points to linked list
    node* header;

    //Utility Function to free memory allocated to the nodes
    void freeMemory()
    {
        node * t;
        while(header != NULL)
        {
            t = header;
            header = header->next;
            delete t;
        }
        header = NULL;
    }

    //Utility Function to check the presence any data in the list
    bool isPresent(int data)
    {
        node *t = header;

        while ( t != NULL )
        {
            if(data == t->data )
                return true;
            t = t->next;
        }

        return false;
    }

public:
    //Default Constructor
    LinkedList():header(NULL) {}

    //Copy Constructor
    LinkedList(const LinkedList &cp)
    {
        node *t = cp.header, *t2;
        header = NULL;
        while(t != NULL)
        {
            t2 = new node;
            t2->data = t->data;
            t2->next = header;
            header = t2;
            t = t->next;
        }

    }

    //Overloaded Assignment Operator
    LinkedList& operator=(const LinkedList &cp)
    {
        if(&cp == this)
            return *this;
        //LinkedList();
        freeMemory();
        node *t = cp.header, *t2;
        header = NULL;
        while(t != NULL)
        {
            t2 = new node;
            t2->data = t->data;
            t2->next = header;
            header = t2;
            t = t->next;
        }

        return *this;

    }

    //Destructor
    ~LinkedList()
    {
        node * t;
        while(header != NULL)
        {
            t = header;
            header = header->next;
            delete t;
        }
        header = NULL;
    }

    //Function that adds element to linked list
    void push(int data)
    {
        node *t = new node;
        t->next = header;
        t->data = data;
        header = t;
    }

    //Displays the linked list in console
    void printList()
    {
        node *t = header;
        while(t != NULL)
        {
            cout<<t->data<<"  ";
            t = t->next;
        }
        cout<<endl;
    }

    //Union Function
    /*
    Algorithim
    1> Create an empty List.
    2> Traverse list1 and add all of its elements to the result.
    3> Traverse list2. If an element of list2 is already present
       in result then do not insert it to result, otherwise insert.
    Time Complexity : O(mn) m is the number of elements in first
       list and n is the number of elements in second list.
    */
    LinkedList unionList(LinkedList list2)
    {
        node *t1= header, *t2 = list2.header;
        LinkedList result;

        while(t1 != NULL)
        {
            result.push(t1->data);
            t1 = t1->next;
        }

        while(t2 != NULL)
        {
            if(!result.isPresent(t2->data))
                result.push(t2->data);
            t2 = t2->next;
        }

        return result;

    }

    //Intersection Function
    /*Algorithim
    1> Create an Empty List.
    2> Traverse list1 and look for its each element in list2,
       if the element is present in list2, then add the element to result
    Time Complexity : O(mn) m is the number of elements in first
       list and n is the number of elements in second list.
    */
    LinkedList intersectList(LinkedList list2)
    {
        node *t1= header;
        LinkedList result;

        while(t1 != NULL)
        {
            if(list2.isPresent(t1->data))
                result.push(t1->data);
            t1 = t1->next;
        }

        return result;
    }

};

int main()
{
    LinkedList list1;
    list1.push(10);
    list1.push(30);
    list1.push(12);
    list1.push(19);
    list1.push(78);
    cout<<"List1 : ";
    list1.printList();

    LinkedList list2;
    list2.push(30);
    list2.push(121);
    list2.push(19);
    list2.push(89);
    cout<<"List2 : ";
    list2.printList();

    LinkedList listUnion = list1.unionList(list2);
    cout<<"Union List : ";
    listUnion.printList();

    LinkedList listIntersect = list1.intersectList(list2);
    cout<<"Intercestion List : ";
    listIntersect.printList();


    return 0;
}

Output :-

List1 : 78  19  12  30  10
List2 : 89  19  121  30
Union List : 89  121  10  30  12  19  78
Intercestion List : 30  19

non-type template-parameter

A non-type template-parameter shall have one of the following (optionally cv-qualified) types:

• integral or enumeration type,
• pointer to object or pointer to function,
• lvalue reference to object or lvalue reference to function,
• pointer to member,
• std::nullptr_t.