#include <cstdlib>
#include <iostream>

using namespace std;
char** myMergeSort(char** listOfWords, int length);
char** merge(char** left, char** right, int, int);

int main() {

	char array[][] = {{'h','1'},
						 {'a'},
						 {'a'},
						 {'r'},
						 {'q'}};

	int size = 7;

	int* result = myMergeSort(array, size);

	for(int i=0; i<size; i++){
		cout << *(result+i) << endl;
	}

	return 0;

}

char** myMergeSort(char** arr, int size) {
	if(size <= 1) return arr;

	int mid =size/2;

	char** left = new char*[mid];
	char** right = new char*[size-mid];
	char** res = new char*[size];

	for(int i=0; i<mid; i++) {
		*(left+i) = *(arr+i);
	}
	for(int i=0; i<size-mid; i++) {
		*(right+i) = *(arr+i+mid);
	}
	left = myMergeSort(left, mid);
	right = myMergeSort(right, size-mid);
	res = merge(left, right, mid, size-mid);

	return res;
}

char** merge(char** left, char** right, int leftsize, int rightsize) {
	char** res = new char*[leftsize+rightsize];
	int count=0;
	int cur_left=0;
	int cur_right=0;

	while(cur_left < leftsize || cur_right < rightsize) {
		if(cur_left < leftsize && cur_right < rightsize) {
			if(*(left+cur_left) <= *(right+cur_right)) {
				*(res+count) = *(left+cur_left);
				cur_left++;
			} else {
				*(res+count) = *(right+cur_right);
				cur_right++;
			}
		} else if(cur_left < leftsize) {
			*(res+count) = *(left+cur_left);
			cur_left++;
		} else if(cur_right < rightsize) {
			*(res+count) = *(right+cur_right);
			cur_right++;
		}
		count++;
	}

	return res;
}