Time limit: 5000ms
Memory limit: 256mb

Description:

You are given n strings and you want to sort them in lexicographical order. One of your firend helped you implemented a program to do the sorting. However, he has something else to do now and the program is not finished yet. It is known that he want to use merge sort to sort these strings and he has implemented most of it. Now you do not want to bother your firend anymore, so you want to finish the program your self. The unfinished program is as follows.

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef const char* string;

void merge(string arr[], int left, int middle, int right) {
  string* temparray = (string*)malloc(sizeof(string) * (right - left + 1));
  int firstleft = left;
  int secondleft = middle + 1;
  int filled = 0;
  while (firstleft <= middle && secondleft <= right) {
    if (strcmp(arr[firstleft], arr[secondleft]) < 0) {
      temparray[filled++] = arr[firstleft++];
    } else {
      temparray[filled++] = arr[secondleft++];
    }
  }
  while (firstleft <= middle) {
    temparray[filled++] = arr[firstleft++];
  }
  while (secondleft <= right) {
    temparray[filled++] = arr[secondleft++];
  }
  for (int i = 0; i <= (right - left); i++) {
    arr[left + i] = temparray[i];
  }
  free(temparray);
}

void mergeSort(string arr[], int left, int right);

int main() {
  int n;
  scanf("%d", &n);
  string* arr = (string*)malloc(sizeof(string) * n);
  for (int i = 0; i < n; i++) {
    char str[1024];
    scanf("%1023s", str);
    arr[i] = strdup(str);
  }
  mergeSort(arr, 0, n - 1);
  for (int i = 0; i < n; i++) {
    printf("%s\n", arr[i]);
  }
}

/* Please keep the code above unchanged.
 * You can only edit the following code.
 */

// Implement merge sort using the given merge function .
void mergeSort(string arr[], int left, int right) {
  // WRITE YOUR OWN CODE HERE
}

Sample input:
10
data
structure
algorithm
binary
tree
stack
c
cuhk
seem
mergesort

Sample output:
algorithm
binary
c
cuhk
data
mergesort
seem
stack
structure
tree