Merge sort

To calculate Merge sort call the Merge_Sort function with (array, starting_index, ending_index).

void Merge(int A[], int p, int q, int r)
{
    int i, j, k, n1 = q - p + 1, n2 = r - q;
//n1=number of element at left, n2=number of element at right
    int L[n1], R[n2];

    for(i = 0; i < n1; i++)
        L[i] = A[p + i];

    for(j = 0; j < n2; j++)
        R[j] = A[q + j + 1];

    for(k = p, i = j = 0; k <= r; k++) {
        if(j >= n2 || (i < n1 && L[i] <= R[j]))
        {
            A[k] = L[i++];
        }
        else
        {
            A[k] = R[j++];
        }
    }
}

void Merge_Sort(int A[], int p, int r)
{
    if(p < r) {
        int q = (p + r) / 2;
        Merge_Sort(A, p, q);
        Merge_Sort(A, q+1, r);
        Merge(A, p, q, r);
    }
}

Selection sort

Selection sort function-

void selection_sort(int arr[], int n)
{
	int j,temp,ipos,imin;

	for(ipos=0;ipos<n-1;ipos++)
	{
		imin=ipos;
		for(j=ipos+1;j<n;j++)
		{
			if(arr[imin]>arr[j])
				imin=j;
		}
		if(ipos!=imin)
		{
			temp=arr[ipos];
			arr[ipos]=arr[imin];
			arr[imin]=temp;
		}
	}
}

Insertion sort

Insertion sort function-

void insertion_sort(int arr[], int n)
{
    int i,j,value;

    for(i=1;i<n;i++)
    {
        value=arr[i];
        for(j=i-1;j>=0 && arr[j]>value;j--)
        {
            arr[j+1]=arr[j];
        }
        arr[j+1]=value;
    }
}

Bubble Sort

Bubble sort function-

void bubble_sort(int arr[], int n)
{
	int i,j,temp;

	for(i=n-1;i>=0;i--)
	{
		for(j=1;j<=i;j++)
		{
			if(arr[j-1]>arr[j])
			{
				temp=arr[j-1];
				arr[j-1]=arr[j];
				arr[j]=temp;
			}
		}
	}
}

Extended euclid algorithm

While the euclidean algorithm simply finds the greatest common divisor of two numbers a and b, The extended euclidean algorithm finds the GCD also factors in addition to x and y such that:

That is, it finds the coefficients by which the GCD of two numbers expressed in terms of the numbers themselves.
Details can be found here and here.

Implementation of extended euclidean algorithm-

int gcd ( int a, int b, int & x, int & y ) {
	if ( a == 0 ) {
		x = 0 ; y = 1 ;
		return b ;
	}
	int x1, y1 ;
	int d = gcd ( b % a, a, x1, y1 ) ;
	x = y1 - ( b / a ) * x1 ;
	y = x1 ;
	return d ;
} 

This is a recursive function, which still returns the GCD of the numbers a and b, But apart from that- the value of x and y passed as reference to the function.

Here is another c++ implementation which uses class to handle the value of x,y and d.  I found it here.

class Euclid {
public:
    i64 x, y, d;
    Euclid() {}
    Euclid(i64 _x, i64 _y, i64 _d) : x(_x), y(_y), d(_d) {}
};
 
Euclid egcd(i64 a, i64 b) {
    if(!b) return Euclid(1, 0, a);
    Euclid r = egcd(b, a % b);
    return Euclid(r.y, r.x - a / b * r.y, r.d);
}

Big Mod

Big Mod algorithm simply use the modular arithmetic to find the value of-

(a^p)%m.

Big Mod recursive approach-

int bigmod ( long long a, int p, int m )
{
    if ( p == 0 )return 1; // If power is 0 ( a ^ 0 ), return 1

    if ( p & 1 ) // If power is odd
    {
        return ( ( a % m ) * ( bigmod ( a, p - 1, m ) ) ) % m;
    }
    else
    {
        long long tmp = bigmod ( a, p / 2, m ); 
        return ( tmp * tmp ) % m;
    }
}

Big Mod Iterative approach-

long long bigmod ( long long a, long long p, long long m )
{
    long long res = 1;
    long long x = a;
    
    while ( p )
    {
        if ( p & 1 ) //p is odd
        {
            res = ( res * x ) % m;
        }
        x = ( x * x ) % m;
        p = p >> 1;
    }

    return res;
}

Factorial factorization

This function calculates the factorization of the given number's factorial.

int factors(int num)
{
    int i,tmp,cnt;
    
    for(i=0;i<max_prime && prime[i]<=num;i++)
    {
        cnt=0;
        tmp=num;
        cout<< prime[i] << " ";
        while(tmp>0)
        {
            cnt+=floor(tmp/prime[i]);
            tmp/=prime[i];
        }
        cout<< cnt << endl;
    }
}