For me, merge sort is quite complex. It requires dividing the list to be sorted in smaller parts and then merging them. It works on divide and conquer philosophy. For example, let us consider an array of 10 elments: int array[] = {2,3,1,4,5,4,2,3,12,10}; In divide section, you will divide in such a way that in every divided part, there are only one element: void divide(int array[],int l,int r) { if ( l != r ) { int mid = ( l + r ) / 2; divide(array,l,mid); divide(array,mid+1,r); merge(array,l,r); } } We start dividing it by middle element. Now, we will merge them: void merge(int array[],int l,int r) { int A[10]; int B[10]; int mid = ( l + r ) / 2; int j = 0; int i; for (i = l; i <= mid; ++i) { A[j++] = array[i]; } j = 0; for (i = mid + 1; i <= r; ++i) { B[j++] = array[i]; } int k = l; for (i = 0,j=0; i <= mid - l && j <= r - mid -1;) { ...
In the previous post, I discussed about selection sort . In this post, I will be talking about insertion sort. What does insertion mean? It means to place something somewhere, to insert something at some place. So basically, it's about placing an element at its sorted position. We have already a sorted array, and we need to place the ith element at its corresponding position. So, the heart of insertion sort is: int key = array[i]; int j = i-1; while (j >= 0 && array[j] > key) { array[j+1] = array[j]; j = j-1; } array[j+1] = key; Start from ith element, look for it's suitable position and place the element right there. A full working code is as follows: #include <stdio.h> int main(int argc, char const *argv[]) { int array[] = {1,2,3,4,10,123,1,8,9}; int n = 9; for (int i = 1; i < n; ++i) { int key = array[i]; int j = i-1; while (j >= 0 && array[j] > key) { ...