bottomupmergesort

unsigned int cointToss()
{
    if (rand() % 2 == 0)
         return 1;
    return 0;
}

//this can be slimmed down even further:
unsigned int cointToss() { return (rand() % 2 ==0); }

bottomupmergesort

void* queueFront(QUEUE* q)
{
    return q->head->next->element;
}

int queueEmpty(QUEUE* q)
{
    return (q->head->next == q->z);
}

bottomupmergesort

void queuePop(QUEUE** q)
{
    qnode* t = (*q)->head->next;
    (*q)->head->next = (*q)->head->next->next;
    (*q)->head->next->prev = (*q)->head;
    free(t);
    (*q)->size--;
}

bottomupmergesort

void queuePush(QUEUE** q, void* element)
{
    qnode* n = new_qnode(element);
    n->prev = (*q)->z->prev;
    n->next = (*q)->z;
    (*q)->z->prev->next = n;
    (*q)->z->prev = n;
    (*q)->size++;
}

bottomupmergesort

qnode* new_qnode(void* element)
{
    qnode* nqn = (struct qnode*)malloc(sizeof(qnode));
    nqn->element = element;
    nqn->prev = NULL;
    nqn->next = NULL;
    return nqn;
}

QUEUE* newQueue()

bottomupmergesort

typedef struct qnode {
    void* element;
    struct qnode* next;
    struct qnode* prev;
}qnode;

typedef struct QUEUE {
    qnode* head;
    qnode* z;
    int size;

bottomupmergesort

#include <iostream>
#include <chrono>
#include "sorted_array_dict.hpp"
#include "list_dict.hpp"
#include "bst_dict.hpp"
using namespace std;


void usinglist()
{

bottomupmergesort

    T2 find(T key)
    {
        int h = N;
        int l = 0;
        while (l < h)
        {
            int mid = (l+h) / 2;
            if (key == arr[mid].key)
                return arr[mid].value;
            if (key < arr[mid].key) h = mid - 1;

bottomupmergesort

    T2 find(T key)
    {
        for (node* itr = head; itr != nullptr; itr = itr->next)
        {
            if (key == itr->key)
                return itr->value;
        }
        return nullItem;
    }

bottomupmergesort

#ifndef DICT_HPP
#define DICT_HPP

//pure virtual class defining the dictionary
//abstract data type interface
template <typename T, typename T2>
class Dict {
    public:
    virtual void insert(T key, T2 value) = 0;
    virtual void remove(T key) = 0;