Insertion Sort, Merge Sort. Time complexity of all sorting algorithms and their comparison.

Insertion Sort,
Merge Sort.
Time complexity of all sorting algorithms and their comparison.

1. ESIT137: Fundamentals of Data Structure
Sanjivani Rural Education Society’s
Sanjivani College of Engineering, Kopargaon-423603
(An Autonomous Institute Affiliated to SavitribaiPhulePune University, Pune)
NACC ‘A’ Grade Accredited, ISO 9001:2015 Certified
Department of Information Technology
(UG Programme -NBA Accredited)
Dr. M.A. Jawale
Professor and Head, Dept. of IT

2. Searching and Sorting
Sorting Algorithms
Insertion Sort,
Merge Sort.
Time complexity of all sorting algorithms and their comparison.
References
Unit-II: Part-III Searching and Sorting Dr. Madhuri Jawale Department of Information Technology

3. Insertion Sort
Insertionsortisasimplesortingalgorithmthatworkssimilarlytothewayyou
sortplayingcardsinyourhands.
Thearrayisvirtuallysplitintoasortedandanunsortedpart.Valuesfromthe
unsortedpartarepickedandplacedinthecorrectpositioninthesortedpart.
Unit-II: Part-III Searching and Sorting Dr. Madhuri Jawale Department of Information Technology

4. Insertion Sort Algorithm
TosortanarrayofsizeNinascendingorderiterateoverthearrayandcompare
thecurrentelement(key)toitspredecessor,ifthekeyelementissmallerthanits
predecessor,compareittotheelementsbefore.
Movethegreaterelementsonepositionuptomakespacefortheswapped
element.
Unit-II: Part-III Searching and Sorting Dr. Madhuri Jawale Department of Information Technology

5. Working of Insertion Sort algorithm
Consideranexample:arr[]:{12,11,13,5,6}
FirstPass:
Initially,thefirsttwoelementsofthearrayarecomparedininsertionsort.
Here,12isgreaterthan11hencetheyarenotintheascendingorderand12is
notatitscorrectposition.Thus,swap11and12.
So,fornow11isstoredinasortedsub-array.
Unit-II: Part-III Searching and Sorting Dr. Madhuri Jawale Department of Information Technology

6. Continue….
SecondPass:
Now,movetothenexttwoelementsandcomparethem.
Here,13isgreaterthan12,thusbothelementsseemstobeinascendingorder,
hence,noswappingwilloccur.12alsostoredinasortedsub-arrayalongwith
11.
ThirdPass:
Now,twoelementsarepresentinthesortedsub-arraywhichare11and12
Movingforwardtothenexttwoelementswhichare13and5
Unit-II: Part-III Searching and Sorting Dr. Madhuri Jawale Department of Information Technology

7. Continue….
Both5and13arenotpresentattheircorrectplacesoswapthem.
Afterswapping,elements12and5arenotsorted,thusswapagain.
Here,again11and5arenotsorted,henceswapagain
Here,5isatitscorrectposition
Unit-II: Part-III Searching and Sorting Dr. Madhuri Jawale Department of Information Technology

8. Continue….
FourthPass:
Now,theelementswhicharepresentinthesortedsub-arrayare5,11and12
Movingtothenexttwoelements13and6
Clearly,theyarenotsorted,thusperformswapbetweenboth.
Now,6issmallerthan12,hence,swapagain.
Unit-II: Part-III Searching and Sorting Dr. Madhuri Jawale Department of Information Technology

9. Continue….
Now,theelementswhicharepresentinthesortedsub-arrayare5,11and12
Here,alsoswappingmakes11and6unsortedhence,swapagain.
Finally,thearrayiscompletelysorted.
Unit-II: Part-III Searching and Sorting Dr. Madhuri Jawale Department of Information Technology

10. Continue….
Unit-II: Part-III Searching and Sorting Dr. Madhuri Jawale Department of Information Technology

11. Continue….
Unit-II: Part-III Searching and Sorting Dr. Madhuri Jawale Department of Information Technology
/* Function to sort an array using insertion sort*/
void insertionSort(intarr[], intn)
{
inti, key, j;
for (i= 1; i< n; i++) {
key = arr[i];
j = i-1;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j -1;
}
arr[j + 1] = key;
}
}

12. Continue….
Unit-II: Part-III Searching and Sorting Dr. Madhuri Jawale Department of Information Technology
// function to print an array of size n
void printArray(intarr[], intn)
{
inti;
for (i= 0; i< n; i++)
printf("%d ", arr[i]);
printf("\n");
}
/* Driver program to test insertion sort */
intmain()
{
intarr[] = { 12, 11, 13, 5, 6 };
intn = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
printArray(arr, n);
return 0;
}

13. Complexity Analysis of Insertion Sort
TimeComplexityofInsertionSort:
Theworst-casetimecomplexityoftheInsertionsortisO(N
2
)
TheaveragecasetimecomplexityoftheInsertionsortisO(N
2
)
ThetimecomplexityofthebestcaseisO(N).
SpaceComplexityofInsertionSort:
TheauxiliaryspacecomplexityofInsertionSortisO(1)
Unit-II: Part-III Searching and Sorting Dr. Madhuri Jawale Department of Information Technology

14. Characteristics of Insertion Sort
Thisalgorithmisoneofthesimplestalgorithmswithasimpleimplementation
Basically,Insertionsortisefficientforsmalldatavalues
Insertionsortisadaptiveinnature,i.e.itisappropriatefordatasetsthatare
alreadypartiallysorted.
Unit-II: Part-III Searching and Sorting Dr. Madhuri Jawale Department of Information Technology

15. Merge Sort
Mergesortisdefinedasasortingalgorithmthatworksbydividinganarrayinto
smallersubarrays,sortingeachsubarray,andthenmergingthesortedsubarrays
backtogethertoformthefinalsortedarray.
Insimpleterms,wecansaythattheprocessofmergesortistodividethearray
intotwohalves,sorteachhalf,andthenmergethesortedhalvesbacktogether.
Thisprocessisrepeateduntiltheentirearrayissorted.
Unit-II: Part-III Searching and Sorting Dr. Madhuri Jawale Department of Information Technology

16. Continue….
Unit-II: Part-III Searching and Sorting Dr. Madhuri Jawale Department of Information Technology

17. How does Merge Sort work?
Mergesortisarecursivealgorithmthatcontinuouslysplitsthearrayinhalfuntil
itcannotbefurtherdividedi.e.,thearrayhasonlyoneelementleft(anarraywith
oneelementisalwayssorted).Thenthesortedsubarraysaremergedintoone
sortedarray.
Letsconsideranarrayarr[]={38,27,43,10}
Initiallydividethearrayintotwoequalhalves:
Unit-II: Part-III Searching and Sorting Dr. Madhuri Jawale Department of Information Technology

18. How does Merge Sort work?
Letsconsideranarrayarr[]={38,27,43,10}
Initiallydividethearrayintotwoequalhalves:
Unit-II: Part-III Searching and Sorting Dr. Madhuri Jawale Department of Information Technology

19. Continue….
Thesesubarraysarefurtherdividedintotwohalves.Nowtheybecomearray
ofunitlengththatcannolongerbedividedandarrayofunitlengthare
alwayssorted.
Unit-II: Part-III Searching and Sorting Dr. Madhuri Jawale Department of Information Technology

20. Continue….
Thesesortedsubarraysaremergedtogether,andwegetbiggersorted
subarrays.
Unit-II: Part-III Searching and Sorting Dr. Madhuri Jawale Department of Information Technology

21. Continue….
Thismergingprocessiscontinueduntilthesortedarrayisbuiltfromthe
smallersubarrays.
Unit-II: Part-III Searching and Sorting Dr. Madhuri Jawale Department of Information Technology

22. Continue….
Unit-II: Part-III Searching and Sorting Dr. Madhuri Jawale Department of Information Technology
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(intarr[], intl, intm, intr)
{
inti, j, k;
intn1 = m -l + 1;
intn2 = r -m;
// Create temp arrays
intL[n1], R[n2];
// Copy data to temp arrays L[] and R[]
for (i= 0; i< n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
// Merge the temp arrays back into arr[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++;
}
k++;
}

23. Continue….
Unit-II: Part-III Searching and Sorting Dr. Madhuri Jawale Department of Information Technology
// 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++;
}
}
// l is for left index and r is right index of the
// sub-array of arrto be sorted
void mergeSort(intarr[], intl, intr)
{
if (l < r) {
intm = l + (r -l) / 2;
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}

24. Continue….
Unit-II: Part-III Searching and Sorting Dr. Madhuri Jawale Department of Information Technology
// Function to print an array
void printArray(intA[], intsize)
{
inti;
for (i= 0; i< size; i++)
printf("%d ", A[i]);
printf("\n");
}
// Driver code
intmain()
{
intarr[] = { 12, 11, 13, 5, 6, 7 };
intarr_size = sizeof(arr) / sizeof(arr[0]);
printf("Given array is \n");
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size -1);
printf("\nSortedarray is \n");
printArray(arr, arr_size);
return 0;
}

25. Complexity Analysis of Merge Sort
TimeComplexity:O(Nlog(N)),MergeSortisarecursivealgorithmandtime
complexitycanbeexpressedasfollowingrecurrencerelation.
T(n) = 2T(n/2) + θ(n)
AuxiliarySpace:O(N),Inmergesortallelementsarecopiedintoanauxiliary
array.SoNauxiliaryspaceisrequiredformergesort.
Unit-II: Part-III Searching and Sorting Dr. Madhuri Jawale Department of Information Technology

26. Applications of Merge Sort
Sortinglargedatasets:Mergesortisparticularlywell-suitedforsortinglarge
datasetsduetoitsguaranteedworst-casetimecomplexityofO(nlogn).
Externalsorting:Mergesortiscommonlyusedinexternalsorting,wherethe
datatobesortedistoolargetofitintomemory.
Customsorting:Mergesortcanbeadaptedtohandledifferentinput
distributions,suchaspartiallysorted,nearlysorted,orcompletelyunsorteddata.
Unit-II: Part-III Searching and Sorting Dr. Madhuri Jawale Department of Information Technology

27. Advantages of Merge Sort
Stability:Mergesortisastablesortingalgorithm,whichmeansitmaintainsthe
relativeorderofequalelementsintheinputarray.
Guaranteedworst-caseperformance:Mergesorthasaworst-casetime
complexityofO(NlogN),whichmeansitperformswellevenonlargedatasets.
Parallelizable:Mergesortisanaturallyparallelizablealgorithm,whichmeansit
canbeeasilyparallelizedtotakeadvantageofmultipleprocessorsorthreads.
Unit-II: Part-III Searching and Sorting Dr. Madhuri Jawale Department of Information Technology

28. Drawbacks of Merge Sort
Spacecomplexity:Mergesortrequiresadditionalmemorytostorethemerged
sub-arraysduringthesortingprocess.
Notin-place:Mergesortisnotanin-placesortingalgorithm,whichmeansit
requiresadditionalmemorytostorethesorteddata.Thiscanbeadisadvantagein
applicationswherememoryusageisaconcern.
Notalwaysoptimalforsmalldatasets:Forsmalldatasets,Mergesorthasa
highertimecomplexitythansomeothersortingalgorithms,suchasinsertionsort.
Thiscanresultinslowerperformanceforverysmalldatasets.
Unit-II: Part-III Searching and Sorting Dr. Madhuri Jawale Department of Information Technology

29. Comparison among Bubble Sort, Selection Sort and Insertion Sort
BubbleSort:
Timecomplexity:O(n
2
)intheworstandaveragecases,O(n)inthebestcase
(whentheinputarrayisalreadysorted)
Spacecomplexity:O(1)
Basicidea:Iteratethroughthearrayrepeatedly,comparingadjacentpairsof
elementsandswappingthemiftheyareinthewrongorder.Repeatuntilthe
arrayisfullysorted..
Unit-II: Part-III Searching and Sorting Dr. Madhuri Jawale Department of Information Technology

30. Comparison among Bubble Sort, Selection Sort and Insertion Sort
SelectionSort:
Timecomplexity:O(n
2
)inallcases(worst,average,andbest)
Spacecomplexity:O(1)
Basicidea:Findtheminimumelementintheunsortedportionofthearrayand
swapitwiththefirstunsortedelement.Repeatuntilthearrayisfullysorted.
Unit-II: Part-III Searching and Sorting Dr. Madhuri Jawale Department of Information Technology

31. Comparison among Bubble Sort, Selection Sort and Insertion Sort
InsertionSort:
Timecomplexity:O(n
2
)intheworstandaveragecases,O(n)inthebestcase
(whentheinputarrayisalreadysorted)
Spacecomplexity:O(1)
Basicidea:Buildupasortedsubarrayfromlefttorightbyinsertingeachnew
elementintoitscorrectpositioninthesubarray.Repeatuntilthearrayisfully
sorted.
Unit-II: Part-III Searching and Sorting Dr. Madhuri Jawale Department of Information Technology

32. Reference
1.RichardF.Gilberg&BehrouzA.Forouzan,“DataStructures:APseudocode
ApproachwithC,SecondEdition”,CengageLearning.
2.EllisHorowitz,SartajSahani,SusanAnderson-Freed“FundamentalsofData
StructuresinC”,UniversitiesPress,2008.
Unit-II: Part-III Searching and Sorting Dr.Madhuri Jawale Department of Information Technology