Merge Sort

#include<iostream>
#include<conio.h>


using namespace std;


//function to merge two halves
// arr[l..m] abd arr[m+1 ... r]

void merge(int arr[], int l, int m, int r)
{
   
    int n1 = m - l + 1; // total elements in first half
    int n2 = r - m;// in second half
    int i = 0, j = 0, k = 0;
    int L[n1], R[n2];

    // copy data to temp arrays
    for ( i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for ( j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    // merge temp arrays back to a[l..r];
    i = 0; j = 0; k = l;
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
                ++i;

        }
        else
        {
            arr[k] = R[j];
            j++;
        }
    }

    /* Copy the remaining elements of L[] , if there are any */
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }

    /* Copy the remaining elements of R[], if there are any */
    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }


}



void mergeSort(int arr[], int l, int r)
{
    if (l < r)
    {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}


void printArray(int A[], int size)
{
    int i;
    for (i = 0; i < size; i++)
        cout << A[i];
    printf("\n");
}


int main()
{
    int arr[] = { 12, 11, 13, 5, 6, 7 };
    int arr_size = sizeof(arr) / sizeof(arr[0]);

    printf("Given array is \n");
    printArray(arr, arr_size);

    mergeSort(arr, 0, arr_size - 1);

    printf("\nSorted array is \n");
    printArray(arr, arr_size);
    getchar();
    return 0;
}

Merge sort on Linked List

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

struct node
{
    int data;
    struct node* next;
};

// function prototypes
struct node* SortedMerge(struct node* a, struct node* b);
void FrontBackSplit(struct node* source, struct node** frontRef, struct node** backRef);

//sorts linked list by changing next pointers
void MergeSort(struct node** headRef)
{
    struct node* head = *headRef;
    struct node* a;
    struct node* b;

    //base case , when there are one or no elements
    if (head == NULL || head->next == NULL)
        return;

    // split head into a nd b sublists
    FrontBackSplit(head, &a, &b);

    // recursively sort sublist
    MergeSort(&a);
    MergeSort(&b);

    // answer = head of the merged list
    *headRef = SortedMerge(a,b);

}

struct node* SortedMerge(struct node* a, struct node* b)
{
    struct node* result = NULL;

    /* Base cases */
    if (a == NULL)
        return(b);
    else if (b == NULL)
        return(a);

    /* Pick either a or b, and recur */
    if (a->data <= b->data)
    {
        result = a;
        result->next = SortedMerge(a->next, b);
    }
    else
    {
        result = b;
        result->next = SortedMerge(a, b->next);
    }
    return(result);
}

// using fast slow pointer techniques to split the list in two halves
void  FrontBackSplit(struct  node* source, struct node** frontRef, struct node** backRef)
{
    struct node* fast;
    struct node* slow;
    if (source == NULL || source->next == NULL)
    {
        //length < 2 cases
        *frontRef = source;
        *backRef = NULL;
    }
    else
    {
        slow = source;
        fast = NULL;

        //advance fast two nodes and slow notes
        while (fast != NULL)
        {
            fast = fast->next;
            if (fast != NULL)
            {
                slow = slow->next;
                fast = fast->next;
            }
        }

        //slow is before midpoint in list , split in two halfs
        *frontRef = source;
        *backRef = slow->next;
        slow->next = NULL;
    }
}

/* Function to print nodes in a given linked list */
void printList(struct node *node)
{
    while (node != NULL)
    {
        printf("%d ", node->data);
        node = node->next;
    }
}


void push(struct node** head_ref, int new_data)
{
    /* allocate node */
    struct node* new_node =
        (struct node*) malloc(sizeof(struct node));

    /* put in the data  */
    new_node->data = new_data;

    /* link the old list off the new node */
    new_node->next = (*head_ref);

    /* move the head to point to the new node */
    (*head_ref) = new_node;
}

int main()
{
  /* Start with the empty list */
 
  struct node* a = NULL;

  /* Let us create a unsorted linked lists to test the functions
   Created lists shall be a: 2->3->20->5->10->15 */
  push(&a, 15);
  push(&a, 10);
  push(&a, 5);
  push(&a, 20);
  push(&a, 3);
  push(&a, 2);

  /* Sort the above created Linked List */
  MergeSort(&a);

  printf("\n Sorted Linked List is: \n");
  printList(a);          

  getchar();
  return 0;
}

Insertion sort

Boundary Cases: Insertion sort takes maximum time to sort if elements are sorted in reverse order. And it takes minimum time (Order of n) when elements are already sorted.

void insertionSort(int arr[], int  n)
{
    int i, key, j;
    for (i = 1; i < n; ++i)
    {
        key = arr[i];
        j = i - 1;

        //move elements between arr[0.. i-1] one position
        //ahead of theie current position, whhich are greater then key
        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            --j;
        }
        arr[j + 1] = key;

    }
}

Optimised bubble sort




void bubbleSort(int arr[], int n)

{

   int i, j;

   bool swapped;

   for (i = 0; i < n; i++)

   {

     swapped = false;

     for (j = 0; j < n-i-1; j++)

     {

        if (arr[j] > arr[j+1])

        {

           swap(&arr[j], &arr[j+1]);

           swapped = true;

        }

     }

 

     //if no elements are swapped by inner loop  , then break

     if (swapped == false)

        break;

   }

}

 

Find the Minimum length Unsorted Subarray, sorting which makes the complete array sorted

#include<iostream>
#include<conio.h>
using namespace std;

void printUnsorted(int arr[], int n);
int main()
{
    int arr[] = { 10, 12, 20, 30, 25, 40, 32, 31, 35, 50, 60 };
    int arr_size = sizeof(arr) / sizeof(arr[0]);
    printUnsorted(arr,arr_size);
    getchar();
    return 0;
}

void printUnsorted(int arr[], int n)
{
    int s = 0, e = n - 1, i, max, min;

    //scan from left to right and find the first element which is
    //greater then its next element
    for (s = 0; s < n - 1; s++)
    {
        if (arr[s] > arr[s + 1])
            break;
    }
    if (s == n - 1)
    {
        printf("the complete array is sorted");
        return;
    }

    //scan from right to left and find the index of first elemnt which is smaller then next element
    for (e = n - 1; e > 0; --e)
    if (arr[e] < arr[e - 1]) break;


    //find the minimum and smallest element between arr[s..e] subarray
    max = arr[s];  min = arr[s];
    for (i = s + 1; i <= e; ++i)
    {
        if (arr[i] > max) max = arr[i];
        if (arr[i] < min) min = arr[i];
    }

    //find the first element in arr[0..s - 1] which is greater than min
    for (i = 0; i < s; i++)
    {
        if (arr[i] > min)
        {
            s = i;
            break;
        }
    }

    //find the first element in arr[e+1 .. n-1] which is greater than min
    for (i = n - 1; i >= e + 1; --i)
    {
        if (arr[i] < max)
        {

            e = i;
            break;
        }
    }

    printf(" The unsorted subarray which makes the given array "
        " sorted lies between the indees %d and %d", s, e);
    return;


}