codelab

Merge sort is based on divide and conquer method. It takes the list to be sorted and divide it in half to create two unsorted lists. The two unsorted lists are then sorted and merged to get a sorted list. The two unsorted lists are sorted by continually calling the merge-sort algorithm; we eventually get a list of size 1 which is sorted. The two lists of size 1 are then merged. Best case : When the array is already sorted O(nlogn). Worst case : When the array is sorted in reverse order O(nlogn). Average case : O(nlogn). Space Complexity: Extra space is required, because space complexity is O(n) for arrays and O(logn) for linked lists. 

A program can show incorrect output when the input is not validated to see whether it is correct or not. The best way of avoiding such situation is that treat all input as a sequence of characters, and then perform the necessary data conversion. We can use getchar() to read all input as a string, and afterward convert the string to the correct data type. #include<stdio.h> #include<ctype.h> #include<stdlib.h> #define MAXBUFFERSIZE 80 void cleartoendofline(void);          /* ANSI function prototype */ void cleartoendofline(void) { char ch; ch = getchar(); while(ch != '\n') ch = getchar(); }

Insertion sort is a simple algorithm that sorts an array one item at a time. When people manually sort something (for example, a deck of playing cards), most use a method that is similar to insertion sort. The algorithm is efficient for small data sets. How insertion sort works:  The second element of an array is compared with the elements that appear before it (only first element in this case). If the second element is smaller than first element, second element is inserted in the position of first element. After first step, first two elements of an array are sorted. The third element of an array is compared with the elements that appears before it (first and second element). If third element is smaller than first element, it is inserted in the position of first element. If third element is larger than first element but, smaller than second element, it is inserted in the position of second element. If third element is larger than both the elements, it is kept in the pos...