Description

Warning! 

Adhere to the Code of Academic Integrity. You may discuss background issues and general strategies with others and seek help from course instructor, but the implementations that you submit must be your own. You are not allowed to work out the detailed coding and solutions with others, copy code from published/Internet sources or let others to do coding for you. If you feel that you cannot complete the assignment on you own, seek help from the course instructor.

1 Sorting Algorithms 

For your first assignment, you will implement two sorting algorithms, Insertion Sort and Merge Sort. Implemented algorithms sort an array of strings into ascending lexicographic order.

Insertion sort 

Insertion sort is a simple sorting algorithm; a comparison sort in which the sorted array is “built” one entry at a time. In every step of insertion sort, an element is taken from the unsorted segment of the array and is “inserted” into the correct position in the already-sorted segment of the array. This is done until no elements remain in the unsorted segment.