3.
Study and Implementation of Array Based Program
a. Searching (Linear Search, Binary Search)
b. Sorting (Bubble, Insertion, Selection, Quick, Merge etc)
c. Merging
b. Sorting (Bubble, Insertion, Selection, Quick, Merge etc)
Sorting refers to rearrangement of a given array or list of elements according to a comparison
operator on the elements. The comparison operator is used to decide the new order of elements in
the respective data structure.
When we have a large amount of data, it can be difficult to deal with it, especially when it is
arranged randomly. When this happens, sorting that data becomes crucial. It is necessary to sort
data in order to make searching easier.
Types of Sorting Techniques
There are various sorting algorithms used in data structures. The following two types of sorting
algorithms can be broadly classified:
1. Comparison-based: We compare the elements in a comparison-based sorting
algorithm)
2. Non-comparison-based: We do not compare the elements in a non-comparison-based
sorting algorithm)
Sorting algorithm
Why Sorting Algorithms are Important
The sorting algorithm is important in Computer Science because it reduces the complexity of a
problem. There is a wide range of applications for these algorithms, including searching
algorithms, database algorithms, divide and conquer methods, and data structure algorithms.
In the following sections, we list some important scientific applications where sorting algorithms
are used
● When you have hundreds of datasets you want to print, you might want to arrange
them in some way.
● Sorting algorithm is used to arrange the elements of a list in a certain order (either
ascending or descending).
● Searching any element in a huge data set becomes easy. We can use Binary search
method for search if we have sorted data. So, Sorting become important here.
● They can be used in software and in conceptual problems to solve more advanced
problems.
Bubble Sort
Bubble sort is a sorting algorithm that compares two adjacent elements and swaps them until
they are in the intended order.
Just like the movement of air bubbles in the water that rise up to the surface, each element of the
array move to the end in each iteration. Therefore, it is called a bubble sort.
Working of Bubble Sort
Suppose we are trying to sort the elements in ascending order.
1. First Iteration (Compare and Swap)
1. Starting from the first index, compare the first and the second elements.
2. If the first element is greater than the second element, they are swapped.
3. Now, compare the second and the third elements. Swap them if they are not in order.
4. The above process goes on until the last element.
Compare the Adjacent
Elements
2. Remaining Iteration
The same process goes on for the remaining iterations.
After each iteration, the largest element among the unsorted elements is placed at the end.
Put the largest element at the end
In each iteration, the comparison takes place up to the last unsorted element.
Compare the adjacent elements
The array is sorted when all the unsorted elements are placed at their correct positions.
The array is sorted if all elements
are kept in the right order
C Program for Bubble Sort Using for Loop
#include <stdio.h>
int main(){
int arr[50], num, x, y, temp;
printf("Please Enter the Number of Elements you want in the array: ");
scanf("%d", &num);
printf("Please Enter the Value of Elements: ");
for(x = 0; x < num; x++)
scanf("%d", &arr[x]);
for(x = 0; x < num - 1; x++){
for(y = 0; y < num - x - 1; y++){
if(arr[y] > arr[y + 1]){
temp = arr[y];
arr[y] = arr[y + 1];
arr[y + 1] = temp;
}
}
}
printf("Array after implementing bubble sort: ");
for(x = 0; x < num; x++){
printf("%d ", arr[x]);
}
return 0;
}
Let's break it down step by step:
1. Declaration of Variables:
● The program starts by declaring an array arr of size 50 to store the elements, along
with variables num, x, y, and temp to be used in the sorting process.
2. Input:
● The program prompts the user to enter the number of elements they want in the
array using the prompt: "Please Enter the Number of Elements you want in the
array: ". The user's input is then stored in the variable num.
● Next, the program prompts the user to input the values of the elements one by one
using the prompt: "Please Enter the Value of Elements: ".
● The elements are stored in the array arr using a for loop.
3. Bubble Sort:
● The program then proceeds to perform the bubble sort algorithm on the array to
arrange the elements in ascending order.
● Two nested for loops are used for iteration. The outer loop (for(x = 0; x < num - 1;
x++)) controls the number of passes through the array, while the inner loop (for(y =
0; y < num - x - 1; y++)) compares adjacent elements and performs swaps if necessary.
4. Within the inner loop:
● The if statement (if(arr[y] > arr[y + 1])) checks if the current element is greater than
the next element.
● If the condition is true, the elements are swapped using a temporary variable temp.
5. Output:
● Finally, the sorted array is printed to the console using the prompt: "Array after
implementing bubble sort: ".
6. Return Statement:
● The main function ends with a return statement return 0; to indicate successful
execution.
The bubble sort algorithm has a time complexity of O(n^2), making it relatively inefficient for large
datasets, but its implementation is straightforward.
Overall, this program allows users to enter elements, sorts them using the bubble sort algorithm,
and then displays the sorted array.
C Program for Bubble Sort Using While Loop
#include <stdio.h>
int main(){
int arr[50], num, x, y, temp;
printf("Please Enter the Number of Elements you want in the array: ");
scanf("%d", &num);
printf("Please Enter the Value of Elements: ");
for(x = 0; x < num; x++)
scanf("%d", &arr[x]);
x = 0;
while(x < num - 1){
y = 0;
while(y < num - x - 1){
if(arr[y] > arr[y + 1]){
temp = arr[y];
arr[y] = arr[y + 1];
arr[y + 1] = temp;
}
y++;
}
x++;
}
printf("Array after implementing bubble sort: ");
for(x = 0; x < num; x++)
printf("%d ", arr[x]);
return 0;
}
Here's a step-by-step explanation of the program:
1. Declaration of Variables:
● The program begins with the declaration of variables including an array arr of
size 50 to store the elements, num to store the number of elements, and x, y, and
temp as loop counters and temporary storage.
2. User Input:
● The program prompts the user to enter the number of elements they want in the
array and reads this value into the variable num.
● Then, the program prompts the user to enter the values of the elements and
stores them in the array arr.
3. Bubble Sort Algorithm:
● The program then enters a nested while loop. The outer loop, controlled by the
variable x, iterates from 0 to num-1.
● Inside the outer loop, the inner loop, controlled by the variable y, iterates from 0
to num-x-1.
● Within the inner loop, adjacent elements of the array are compared, and if they
are in the wrong order, they are swapped.
4. Output:
● After the array is sorted using the bubble sort algorithm, the program prints the
sorted array to the console.
5. Exiting the Program:
● Finally, the main function returns 0, indicating successful execution of the
program.
In summary, the program first takes user input for the number of elements and the values of the
elements. It then sorts the array using the bubble sort algorithm and prints the sorted array. This
algorithm works well for small data sets but may not be the most efficient for larger arrays due to
its time complexity.
Here's a line-by-line explanation of the provided code:
#include <stdio.h>
This line includes the standard input-output header file, allowing the program to use input and
output functions.
c
void bubbleSortExample(int arr[], int num){
int x, y, temp;
for(x = 0; x < num - 1; x++){
for(y = 0; y < num - x - 1; y++){
if(arr[y] > arr[y + 1]){
temp = arr[y];
arr[y] = arr[y + 1];
arr[y + 1] = temp;
}
}
}
}
In this part, a function called bubbleSortExample is defined. It takes an array of integers arr[]
and the number of elements num as parameters. Inside the function, the bubble sort logic is
implemented using nested loops to compare adjacent elements and swap them if they are in the
wrong order.
c
int main(){
int arr[50], n, x;
printf("Please Enter the Number of Elements you want in the array: ");
scanf("%d", &n);
printf("Please Enter the Value of Elements: ");
for(x = 0; x < n; x++)
scanf("%d", &arr[x]);
bubbleSortExample(arr, n);
printf("Array after implementing bubble sort: ");
for(x = 0; x < n; x++){
printf("%d ", arr[x]);
}
return 0;
}
The main function is where the program starts its execution. It does the following:
● Declares an array arr[], and two integers n and x.
● Prompts the user to enter the number of elements and their values. The entered values
are stored in the array arr[].
● Calls the bubbleSortExample function to sort the array using the bubble sort algorithm.
● Prints the sorted array to the console.
c
return 0;
}
This line marks the end of the main function and indicates the successful execution of the
program.
The program effectively sorts the user-provided array using the bubble sort algorithm and then
prints the sorted array to the console.
C Program for Bubble Sort Using Functions
In this C program for bubble sort, we will create a user-defined function and write down the
mechanism of sorting the array elements inside it. Here’s how to implement bubble sort in C
using functions.
#include <stdio.h>
void bubbleSortExample(int arr[], int num){
int x, y, temp;
for(x = 0; x < num - 1; x++){
for(y = 0; y < num - x - 1; y++){
if(arr[y] > arr[y + 1]){
temp = arr[y];
arr[y] = arr[y + 1];
arr[y + 1] = temp;
}
}
}
}
int main(){
int arr[50], n, x;
printf("Please Enter the Number of Elements you want in the array: ");
scanf("%d", &n);
printf("Please Enter the Value of Elements: ");
for(x = 0; x < n; x++)
scanf("%d", &arr[x]);
bubbleSortExample(arr, n);
printf("Array after implementing bubble sort: ");
for(x = 0; x < n; x++){
printf("%d ", arr[x]);
}
return 0;
}
Here's a line-by-line explanation of the provided code:
#include <stdio.h>
This line includes the standard input-output header file, which allows the program to use input
and output functions.
void bubbleSortExample(int arr[], int num){
This line defines a function bubbleSortExample that takes an array of integers arr[] and the
number of elements num as parameters.
int x, y, temp;
for(x = 0; x < num - 1; x++){
for(y = 0; y < num - x - 1; y++){
if(arr[y] > arr[y + 1]){
temp = arr[y];
arr[y] = arr[y + 1];
arr[y + 1] = temp;
}
}
}
}
This section of code inside the bubbleSortExample function defines the bubble sort algorithm. It
iterates through the array using nested loops and swaps adjacent elements if they are in the
wrong order, effectively sorting the array in ascending order.
c
int main(){
This line defines the main function, the entry point of the program.
c
int arr[50], n, x;
printf("Please Enter the Number of Elements you want in the array: ");
scanf("%d", &n);
printf("Please Enter the Value of Elements: ");
for(x = 0; x < n; x++)
scanf("%d", &arr[x]);
bubbleSortExample(arr, n);
printf("Array after implementing bubble sort: ");
for(x = 0; x < n; x++){
printf("%d ", arr[x]);
}
In the main function:
● An array arr[], and two integers n and x are declared.
● The user is prompted to enter the number of elements and these values are stored in n.
● The user is prompted to enter the values of the elements which are then stored in the
array arr[].
● The bubbleSortExample function is called to sort the array.
● The sorted array is printed to the console.
c
return 0;
}
This line marks the end of the main function and indicates the successful execution of the
program.
I hope this breakdown helps! If you have further questions or need additional clarification on any
part of the program, feel free to ask!
Insertion Sort Algorithm
Insertion sort is a sorting algorithm that places an unsorted element at its suitable place in each
iteration.
Insertion sort works similarly as we sort cards in our hand in a card game.
We assume that the first card is already sorted, then we select an unsorted card. If the unsorted
card is greater than the card in hand, it is placed on the right, otherwise, to the left. In the same
way, other unsorted cards are taken and put in their right place.
Working of Insertion Sort
Suppose we need to sort the following array.
Initial array
1. The first element in the array is assumed to be sorted. Take the second element and store
it separately in key.
Compare key with the first element. If the first element is greater than key, then key is
placed in front of the first element.
If the first element is
greater than key, then key is placed in front of the first element.
2. Now, the first two elements are sorted.
Take the third element and compare it with the elements on the left of it. Placed it just
behind the element smaller than it. If there is no element smaller than it, then place it at
the beginning of the array.
Place 1 at the beginning
3. Similarly, place every unsorted element at its correct position.
Place 4 behind 1
Place 3 behind 1 and the array is
sorted
Insertion Sort Algorithm
insertionSort(array)
mark first element as sorted
for each unsorted element X
'extract' the element X
for j <- lastSortedIndex down to 0
if current element j > X
move sorted element to the right by 1
break loop and insert X here
end insertionSort
// Insertion sort in C
#include <stdio.h>
// Function to print an array
void printArray(int array[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", array[i]);
}
printf("\n");
}
void insertionSort(int array[], int size) {
for (int step = 1; step < size; step++) {
int key = array[step];
int j = step - 1;
// Compare key with each element on the left of it until an element smaller than
// it is found.
// For descending order, change key<array[j] to key>array[j].
while (key < array[j] && j >= 0) {
array[j + 1] = array[j];
--j;
}
array[j + 1] = key;
}
}
// Driver code
int main() {
int data[] = {9, 5, 1, 4, 3};
int size = sizeof(data) / sizeof(data[0]);
insertionSort(data, size);
printf("Sorted array in ascending order:\n");
printArray(data, size);
}
Here's a breakdown of the program:
c
#include <stdio.h>
This code includes the standard input-output header file, allowing the program to use input and
output functions.
c
void printArray(int array[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", array[i]);
}
printf("\n");
}
The printArray function is defined to print the elements of an array. It takes an array and its
size as parameters and prints each element followed by a space.
c
void insertionSort(int array[], int size) {
for (int step = 1; step < size; step++) {
int key = array[step];
int j = step - 1;
// Compare key with each element on the left of it until an element
smaller than
// it is found.
// For descending order, change key < array[j] to key > array[j].
while (key < array[j] && j >= 0) {
array[j + 1] = array[j];
--j;
}
array[j + 1] = key;
}
}
The insertionSort function implements the insertion sort algorithm. It iterates through the
array, compares the key with each element to its left, and shifts the elements to the right until
the correct position for the key is found.
c
int main() {
int data[] = {9, 5, 1, 4, 3};
int size = sizeof(data) / sizeof(data[0]);
insertionSort(data, size);
printf("Sorted array in ascending order:\n");
printArray(data, size);
}
In the main function:
● An array data[] containing unsorted integers is defined.
● The size of the array is calculated using the sizeof operator.
● The insertionSort function is called to sort the array.
● The sorted array is printed to the console using the printArray function.
This program demonstrates the functionality of the insertion sort algorithm by sorting the
provided array of integers and then printing the sorted array to the console.
Selection Sort Algorithm
Selection sort is a sorting algorithm that selects the smallest element from an unsorted list in each
iteration and places that element at the beginning of the unsorted list.
Working of Selection Sort
1. Set the first element as minimum.
Select first element as minimum
2. Compare minimum with the second element. If the second element is smaller than
minimum, assign the second element as minimum.
Compare minimum with the third element. Again, if the third element is smaller, then
assign minimum to the third element otherwise do nothing. The process goes on until the
last element. Compare minimum with
the remaining elements
3. After each iteration, minimum is placed in the front of the unsorted list.
Swap the first with minimum
4. For each iteration, indexing starts from the first unsorted element. Step 1 to 3 are repeated
until all the elements are placed at their correct positions.
The first iteration
The second iteration
The third iteration
The fourth iteration
Selection Sort Algorithm
selectionSort(array, size)
repeat (size - 1) times
set the first unsorted element as the minimum
for each of the unsorted elements
if element < currentMinimum
set element as new minimum
swap minimum with first unsorted position
end selectionSort
Selection Sort Code in
// Selection sort in C
#include <stdio.h>
// function to swap the the position of two elements
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void selectionSort(int array[], int size) {
for (int step = 0; step < size - 1; step++) {
int min_idx = step;
for (int i = step + 1; i < size; i++) {
// To sort in descending order, change > to < in this line.
// Select the minimum element in each loop.
if (array[i] < array[min_idx])
min_idx = i;
}
// put min at the correct position
swap(&array[min_idx], &array[step]);
}
}
// function to print an array
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d ", array[i]);
}
printf("\n");
}
// driver code
int main() {
int data[] = {20, 12, 10, 15, 2};
int size = sizeof(data) / sizeof(data[0]);
selectionSort(data, size);
printf("Sorted array in Acsending Order:\n");
printArray(data, size);
}
Here's a breakdown of the program:
c
#include <stdio.h>
Open in:
Code Editor
This line includes the standard input-output header file, allowing the program to use input
and output functions.
c
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
Open in:
Code Editor
The swap function is defined to swap the positions of two elements in an array. It takes
pointers to two integers as parameters and swaps their values.
c
void selectionSort(int array[], int size) {
for (int step = 0; step < size - 1; step++) {
int min_idx = step;
for (int i = step + 1; i < size; i++) {
if (array[i] < array[min_idx])
min_idx = i;
}
swap(&array[min_idx], &array[step]);
}
}
Open in:
Code Editor
The selectionSort function implements the selection sort algorithm. It iteratively selects the
minimum element from the unsorted portion of the array and swaps it with the first
unsorted element. This process effectively partitions the array into a sorted and an
unsorted region, and the sorted region grows with each iteration.
c
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d ", array[i]);
}
printf("\n");
}
Open in:
Code Editor
The printArray function is used to print the elements of an array. It iterates through the
array and prints each element, followed by two spaces. After printing all elements, it
inserts a newline character to move to the next line for better formatting.
c
int main() {
int data[] = {20, 12, 10, 15, 2};
int size = sizeof(data) / sizeof(data[0]);
selectionSort(data, size);
printf("Sorted array in Acsending Order:\n");
printArray(data, size);
}
Open in:
Code Editor
In the main` function:
● An array data[] containing unsorted integers is defined.
● The of the array is calculated using the sizeof operator.
● The selectionSort function is called to sort the array.
● The sorted array is printed to the console using the printArray function with a
message indicating the nature of the output.
The program effectively sorts the user-provided array using the selection sort algorithm
and then prints the sorted array to the console.
Selection Sort Complexity
Time Complexity
Best O(n2)
Worst O(n2)
Average O(n2)
Space Complexity O(1)
Stability No
Cycle Number of Comparison
1st (n-1)
2nd (n-2)
3rd (n-3)
... ...
last 1
Number of comparisons: (n - 1) + (n - 2) + (n - 3) + ..... + 1 = n(n - 1) / 2 nearly equals to n2.
Complexity = O(n2)
Also, we can analyze the complexity by simply observing the number of loops. There are 2 loops
so the complexity is n*n = n2.
Time Complexities:
● Worst Case Complexity: O(n2)
If we want to sort in ascending order and the array is in descending order then, the worst
case occurs.
● Best Case Complexity: O(n2)
It occurs when the array is already sorted
● Average Case Complexity: O(n2)
It occurs when the elements of the array are in jumbled order (neither ascending nor
descending).
Quicksort Algorithm
Quicksort is a sorting algorithm based on the divide and conquer approach where
1. An array is divided into subarrays by selecting a pivot element (element selected from the
array).
While dividing the array, the pivot element should be positioned in such a way that
elements less than pivot are kept on the left side and elements greater than pivot are on
the right side of the pivot.
2. The left and right subarrays are also divided using the same approach. This process
continues until each subarray contains a single element.
3. At this point, elements are already sorted. Finally, elements are combined to form a
sorted array.
Working of Quicksort Algorithm
1. Select the Pivot Element
There are different variations of quicksort where the pivot element is selected from different
positions. Here, we will be selecting the rightmost element of the array as the pivot element.
Select a pivot element
2. Rearrange the Array
Now the elements of the array are rearranged so that elements that are smaller than the pivot are
put on the left and the elements greater than the pivot are put on the right.
Put all the smaller
elements on the left and greater on the right of pivot element
Here's how we rearrange the array:
1. A pointer is fixed at the pivot element. The pivot element is compared with the elements
beginning from the first index.
Comparison of
pivot element with element beginning from the first index
2. If the element is greater than the pivot element, a second pointer is set for that element.
If the element is
greater than the pivot element, a second pointer is set for that element.
3. Now, pivot is compared with other elements. If an element smaller than the pivot element
is reached, the smaller element is swapped with the greater element found earlier.
Pivot is compared
with other elements.
4. Again, the process is repeated to set the next greater element as the second pointer. And,
swap it with another smaller element.
The process is
repeated to set the next greater element as the second pointer.
5. The process goes on until the second last element is reached.
The process goes
on until the second last element is reached.
6. Finally, the pivot element is swapped with the second pointer.
Finally, the pivot
element is swapped with the second pointer.
3. Divide Subarrays
Pivot elements are again chosen for the left and the right sub-parts separately. And, step 2 is
repeated.
Select pivot element of in
each half and put at correct place using recursion
The subarrays are divided until each subarray is formed of a single element. At this point, the
array is already sorted.
Quick Sort Algorithm
quickSort(array, leftmostIndex, rightmostIndex)
if (leftmostIndex < rightmostIndex)
pivotIndex <- partition(array,leftmostIndex, rightmostIndex)
quickSort(array, leftmostIndex, pivotIndex - 1)
quickSort(array, pivotIndex, rightmostIndex)
partition(array, leftmostIndex, rightmostIndex)
set rightmostIndex as pivotIndex
storeIndex <- leftmostIndex - 1
for i <- leftmostIndex + 1 to rightmostIndex
if element[i] < pivotElement
swap element[i] and element[storeIndex]
storeIndex++
swap pivotElement and element[storeIndex+1]
return storeIndex + 1
Visual Illustration of Quicksort Algorithm
You can understand the working of quicksort algorithm with the help of the illustrations below.
Sorting the elements on the left of pivot using recursion
Sorting the elements on the right of pivot using recursion
// Quick sort in C
#include <stdio.h>
// function to swap elements
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
// function to find the partition position
int partition(int array[], int low, int high) {
// select the rightmost element as pivot
int pivot = array[high];
// pointer for greater element
int i = (low - 1);
// traverse each element of the array
// compare them with the pivot
for (int j = low; j < high; j++) {
if (array[j] <= pivot) {
// if element smaller than pivot is found
// swap it with the greater element pointed by i
i++;
// swap element at i with element at j
swap(&array[i], &array[j]);
}
}
// swap the pivot element with the greater element at i
swap(&array[i + 1], &array[high]);
// return the partition point
return (i + 1);
}
void quickSort(int array[], int low, int high) {
if (low < high) {
// find the pivot element such that
// elements smaller than pivot are on left of pivot
// elements greater than pivot are on right of pivot
int pi = partition(array, low, high);
// recursive call on the left of pivot
quickSort(array, low, pi - 1);
// recursive call on the right of pivot
quickSort(array, pi + 1, high);
}
}
// function to print array elements
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d ", array[i]);
}
printf("\n");
}
// main function
int main() {
int data[] = {8, 7, 2, 1, 0, 9, 6};
int n = sizeof(data) / sizeof(data[0]);
printf("Unsorted Array\n");
printArray(data, n);
// perform quicksort on data
quickSort(data, 0, n - 1);
printf("Sorted array in ascending order: \n");
printArray(data, n);
}
Quicksort Complexity
Time Complexity
Best O(n*log n)
Worst O(n2)
Average O(n*log n)
Space Complexity O(log n)
Stability No
1. Time Complexities
● Worst Case Complexity [Big-O]: O(n2)
It occurs when the pivot element picked is either the greatest or the smallest element.
This condition leads to the case in which the pivot element lies in an extreme end of the
sorted array. One sub-array is always empty and another sub-array contains n - 1
elements. Thus, quicksort is called only on this sub-array.
However, the quicksort algorithm has better performance for scattered pivots.
● Best Case Complexity [Big-omega]: O(n*log n)
It occurs when the pivot element is always the middle element or near to the middle
element.
● Average Case Complexity [Big-theta]: O(n*log n)
It occurs when the above conditions do not occur.
2. Space Complexity
The space complexity for quicksort is O(log n).
Quicksort Applications
Quicksort algorithm is used when
● the programming language is good for recursion
● time complexity matters
● space complexity matters
c. Merging- (Merge Sort)
#include <stdio.h>
#define max 10
int a[11] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0 };
int b[10];
void merging(int low, int mid, int high) {
int l1, l2, i;
for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) {
if(a[l1] <= a[l2])
b[i] = a[l1++];
else
b[i] = a[l2++];
}
while(l1 <= mid)
b[i++] = a[l1++];
while(l2 <= high)
b[i++] = a[l2++];
for(i = low; i <= high; i++)
a[i] = b[i];
}
void sort(int low, int high) {
int mid;
if(low < high) {
mid = (low + high) / 2;
sort(low, mid);
sort(mid+1, high);
merging(low, mid, high);
} else {
return;
}
}
int main() {
int i;
printf("List before sorting\n");
for(i = 0; i <= max; i++)
printf("%d ", a[i]);
sort(0, max);
printf("\nList after sorting\n");
for(i = 0; i <= max; i++)
printf("%d ", a[i]);
}