Merge sort algorithm

Jun 2, 2021Download as pptx, pdf1 like1,271 views

This power point presentation will give you the knowledge of merge sort algorithm how it works with a given problem solving example. It also describe about the time complexity of merge sort algorithm, and the program in c .

Prepared by:-
Sruti sen patra
Merge sort

Definition:-
Merge sort is one of the most efficient sorting algorithms. It works
on the principle of Divide and Conquer. Merge sort repeatedly
breaks down a list into several sub lists until each sub list consists
of a single element and merging those sub lists in a manner that
results into a sorted list.
Divide and conquer rule:-
A divide-and-conquer algorithm recursively breaks down a
problem into two or more sub-problems of the same or
related type, until these become simple enough to be solved
directly. The solutions to the sub-problems are then
combined to give a solution to the original problem.

Algorithm(divide)
Mergesort(A, lb , ub,)
{
If(lb < ub)
{
Mid = lb+ub/2
Mergesort (A,lb,mid);
Mergesort (A,mid+1,ub);
Merge (A,lb,mid,ub)
}
}

Algorithm(Merge)
Mergesort( A, lb , mid , ub)
{
i=lb;
J=mid +1;
K= lb;
While ( i<=mid && j<=ub)
{
If(a[i]<=a[j])
{
b[k]=a[i]
i++;

Algorithm(merge)
}
Else
b[k]=a[j] ;
J++;
}
K++;
}}
If(i>mid)
{ while (j< =ub)
B[k]=a[j];
J++;
K++;

Algorithm(merge)
}
Else
{
While (i<=mid)
B[k]=a[i];
i++;
K++;
}
}
For(k=lb; k <=ub ; k++)
{ a[k]= b[k];
}}

Time complexity:-
Merge Sort is a recursive algorithm and time
complexity can be expressed as following recurrence
relation.
T(n) = 2T(n/2) + n
 Recurrence tree method:-
Recursion Tree is another method for solving the recurrence
relations. A recursion tree is a tree where each node represents the cost
of a certain recursive sub-problem. We sum up the values in each node
to get the cost of the entire algorithm.

The solution of the above recurrence is O(nLogn). The list
of size N is divided into a max of Logn parts, and the
merging of all sublists into a single list takes O(N) time, the
worst-case run time of this algorithm is O(nLogn)
Best Case Time Complexity: O(n*log n)
Worst Case Time Complexity: O(n*log n)
Average Time Complexity: O(n*log n)
The time complexity of MergeSort is O(n*Log n) in all the 3
cases (worst, average and best) as the mergesort always
divides the array into two halves and takes linear time to
merge two halves.

The document discusses divide and conquer algorithms. It describes divide and conquer as a design strategy that involves dividing a problem into smaller subproblems, solving the subproblems recursively, and combining the solutions. It provides examples of divide and conquer algorithms like merge sort, quicksort, and binary search. Merge sort works by recursively sorting halves of an array until it is fully sorted. Quicksort selects a pivot element and partitions the array into subarrays of smaller and larger elements, recursively sorting the subarrays. Binary search recursively searches half-intervals of a sorted array to find a target value.

Binary search tree(bst)Hossain Md Shakhawat

Data Structures : hashing (1)Home

HashingAmar Jukuntla

Hashing is a technique used to uniquely identify objects by assigning each object a key, such as a student ID or book ID number. A hash function converts large keys into smaller keys that are used as indices in a hash table, allowing for fast lookup of objects in O(1) time. Collisions, where two different keys hash to the same index, are resolved using techniques like separate chaining or linear probing. Common applications of hashing include databases, caches, and object representation in programming languages.

Quick sortInternational Islamic University

The document discusses the quicksort algorithm. It begins by stating the learning goals which are to explain how quicksort works, compare it to other sorting algorithms, and discuss its advantages and disadvantages. It then provides an introduction and overview of quicksort, describing how it uses a divide and conquer approach. The document goes on to explain the details of how quicksort partitions arrays and provides examples. It analyzes the best, average, and worst case complexities of quicksort and discusses its strengths and limitations.

Dinive conquer algorithmMohd Arif

The document discusses the divide and conquer algorithm design technique. It begins by explaining the basic approach of divide and conquer which is to (1) divide the problem into subproblems, (2) conquer the subproblems by solving them recursively, and (3) combine the solutions to the subproblems into a solution for the original problem. It then provides merge sort as a specific example of a divide and conquer algorithm for sorting a sequence. It explains that merge sort divides the sequence in half recursively until individual elements remain, then combines the sorted halves back together to produce the fully sorted sequence.

Divide and ConquerDr Shashikant Athawale

The document discusses the divide and conquer algorithm design paradigm. It begins by defining divide and conquer as recursively breaking down a problem into smaller sub-problems, solving the sub-problems, and then combining the solutions to solve the original problem. Some examples of problems that can be solved using divide and conquer include binary search, quicksort, merge sort, and the fast Fourier transform algorithm. The document then discusses control abstraction, efficiency analysis, and uses divide and conquer to provide algorithms for large integer multiplication and merge sort. It concludes by defining the convex hull problem and providing an example input and output.

Bfs and DfsMasud Parvaze

Algorithms Lecture 2: Analysis of Algorithms IMohamed Loey

This document discusses analysis of algorithms and time complexity. It explains that analysis of algorithms determines the resources needed to execute algorithms. The time complexity of an algorithm quantifies how long it takes. There are three cases to analyze - worst case, average case, and best case. Common notations for time complexity include O(1), O(n), O(n^2), O(log n), and O(n!). The document provides examples of algorithms and determines their time complexity in different cases. It also discusses how to combine complexities of nested loops and loops in algorithms.

B and B+ treeAshish Arun

Representation of binary tree in memoryRohini Shinde

There are two ways to represent a binary tree in memory: sequential representation which uses a single linear array to store the tree, and linked representation which uses three parallel arrays (INFO, LEFT, and RIGHT) along with a ROOT pointer to link nodes. The sequential representation stores the root at index 0 of the array and children at calculated indices, while the linked representation stores the data, left child index, and right child index of each node in the parallel arrays.

daa-unit-3-greedy methodhodcsencet

The document discusses the greedy method algorithmic approach. It provides an overview of greedy algorithms including that they make locally optimal choices at each step to find a global optimal solution. The document also provides examples of problems that can be solved using greedy methods like job sequencing, the knapsack problem, finding minimum spanning trees, and single source shortest paths. It summarizes control flow and applications of greedy algorithms.

Merge sort algorithmShubham Dwivedi

Strassen's matrix multiplicationMegha V

The document discusses Strassen's algorithm for matrix multiplication. It begins by explaining traditional matrix multiplication that has a time complexity of O(n3). It then explains how the divide and conquer strategy can be applied by dividing the matrices into smaller square sub-matrices. Strassen improved upon this by reducing the number of multiplications from 8 to 7 terms, obtaining a time complexity of O(n2.81). His key insight was applying different equations on the sub-matrix multiplication formulas to minimize operations.

Brute force methodpriyankabhansali217

The document discusses brute force and exhaustive search approaches to solving problems. It provides examples of how brute force can be applied to sorting, searching, and string matching problems. Specifically, it describes selection sort and bubble sort as brute force sorting algorithms. For searching, it explains sequential search and brute force string matching. It also discusses using brute force to solve the closest pair, convex hull, traveling salesman, knapsack, and assignment problems, noting that brute force leads to inefficient exponential time algorithms for TSP and knapsack.

Graph coloring using backtrackingshashidharPapishetty

This document summarizes graph coloring using backtracking. It defines graph coloring as minimizing the number of colors used to color a graph. The chromatic number is the fewest colors needed. Graph coloring is NP-complete. The document outlines a backtracking algorithm that tries assigning colors to vertices, checks if the assignment is valid (no adjacent vertices have the same color), and backtracks if not. It provides pseudocode for the algorithm and lists applications like scheduling, Sudoku, and map coloring.

Merge sort algorithm power point presentationUniversity of Science and Technology Chitttagong

Quick Sort , Merge Sort , Heap SortMohammed Hussein

The document discusses various sorting algorithms that use the divide-and-conquer approach, including quicksort, mergesort, and heapsort. It provides examples of how each algorithm works by recursively dividing problems into subproblems until a base case is reached. Code implementations and pseudocode are presented for key steps like partitioning arrays in quicksort, merging sorted subarrays in mergesort, and adding and removing elements from a heap data structure in heapsort. The algorithms are compared in terms of their time and space complexity and best uses.

Binary Heap Tree, Data Structure Anand Ingle

Asymptotic notationDr Shashikant Athawale

This document discusses asymptotic notations that are used to characterize an algorithm's efficiency. It introduces Big-Oh, Big-Omega, and Theta notations. Big-Oh gives an upper bound on running time. Big-Omega gives a lower bound. Theta gives both upper and lower bounds, representing an algorithm's exact running time. Examples are provided for each notation. Time complexity is also introduced, which describes how the time to solve a problem changes with problem size. Worst-case time analysis provides an upper bound on runtime.

Optimal binary search tree dynamic programmingP. Subathra Kishore, KAMARAJ College of Engineering and Technology, Madurai

The document discusses optimal binary search trees (OBST) and describes the process of creating one. It begins by introducing OBST and noting that the method can minimize average number of comparisons in a successful search. It then shows the step-by-step process of calculating the costs for different partitions to arrive at the optimal binary search tree for a given sample dataset with keys and frequencies. The process involves calculating Catalan numbers for each partition and choosing the minimum cost at each step as the optimal is determined.

Breadth First Search & Depth First SearchKevin Jadiya

Design and Analysis of AlgorithmsArvind Krishnaa

This document summarizes a lecture on algorithms and graph traversal techniques. It discusses: 1) Breadth-first search (BFS) and depth-first search (DFS) algorithms for traversing graphs. BFS uses a queue while DFS uses a stack. 2) Applications of BFS and DFS, including finding connected components, minimum spanning trees, and bi-connected components. 3) Identifying articulation points to determine biconnected components in a graph. 4) The 0/1 knapsack problem and approaches for solving it using greedy algorithms, backtracking, and branch and bound search.

Data structures question paper anna universitysangeethajames07

This document contains a data structures question paper from Anna University. It has two parts: Part A contains 10 short answer questions covering topics like ADT, linked stacks, graph theory, algorithm analysis, binary search trees, and more. Part B contains 5 long answer questions each worth 16 marks. Topics include algorithms for binary search, linear search, recursion, sorting, trees, graphs, files, and more. Students are required to write algorithms, analyze time complexity, and provide examples for each question.

Asymptotic NotationProtap Mondal

The document discusses algorithm analysis and asymptotic notation. It defines algorithm analysis as comparing algorithms based on running time and other factors as problem size increases. Asymptotic notation such as Big-O, Big-Omega, and Big-Theta are introduced to classify algorithms based on how their running times grow relative to input size. Common time complexities like constant, logarithmic, linear, quadratic, and exponential are also covered. The properties and uses of asymptotic notation for equations and inequalities are explained.

sparse matrix in data structureMAHALAKSHMI P

This document discusses sparse matrices. It defines a sparse matrix as a matrix with more zero values than non-zero values. Sparse matrices can save space by only storing the non-zero elements and their indices rather than allocating space for all elements. Two common representations for sparse matrices are the triplet representation, which stores the non-zero values and their row and column indices, and the linked representation, which connects the non-zero elements. Applications of sparse matrices include solving large systems of equations.

Quick SortShweta Sahu

The document discusses sorting algorithms and randomized quicksort. It explains that quicksort is an efficient sorting algorithm that was developed by Tony Hoare in 1960. The quicksort algorithm works by picking a pivot element and reordering the array so that all smaller elements come before the pivot and larger elements come after. It then recursively applies this process to the subarrays. Randomized quicksort improves upon quicksort by choosing the pivot element randomly, making the expected performance of the algorithm good for any input.

linear search and binary searchZia Ush Shamszaman

linear search and binary search, Class lecture of Data Structure and Algorithms and Python. Stack, Queue, Tree, Python, Python Code, Computer Science, Data, Data Analysis, Machine Learning, Artificial Intellegence, Deep Learning, Programming, Information Technology, Psuedocide, Tree, pseudocode, Binary Tree, Binary Search Tree, implementation, Binary search, linear search, Binary search operation, real-life example of binary search, linear search operation, real-life example of linear search, example bubble sort, sorting, insertion sort example, stack implementation, queue implementation, binary tree implementation, priority queue, binary heap, binary heap implementation, object-oriented programming, def, in BST, Binary search tree, Red-Black tree, Splay Tree, Problem-solving using Binary tree, problem-solving using BST, inorder, preorder, postorder

Brute Force and Divide & Conquer Techniquessusered62011

Daa chapter 2B.Kirron Reddi

The document discusses the divide and conquer algorithm design technique. It begins by defining divide and conquer as breaking a problem down into smaller subproblems, solving the subproblems, and then combining the solutions to solve the original problem. It then provides examples of applying divide and conquer to problems like matrix multiplication and finding the maximum subarray. The document also discusses analyzing divide and conquer recurrences using methods like recursion trees and the master theorem.

More Related Content

What's hot (20)

Algorithms Lecture 2: Analysis of Algorithms IMohamed Loey

B and B+ treeAshish Arun

Representation of binary tree in memoryRohini Shinde

daa-unit-3-greedy methodhodcsencet

Merge sort algorithmShubham Dwivedi

Strassen's matrix multiplicationMegha V

Brute force methodpriyankabhansali217

Graph coloring using backtrackingshashidharPapishetty

Merge sort algorithm power point presentationUniversity of Science and Technology Chitttagong

Quick Sort , Merge Sort , Heap SortMohammed Hussein

Binary Heap Tree, Data Structure Anand Ingle

Asymptotic notationDr Shashikant Athawale

Optimal binary search tree dynamic programmingP. Subathra Kishore, KAMARAJ College of Engineering and Technology, Madurai

Breadth First Search & Depth First SearchKevin Jadiya

Design and Analysis of AlgorithmsArvind Krishnaa

Data structures question paper anna universitysangeethajames07

Asymptotic NotationProtap Mondal

sparse matrix in data structureMAHALAKSHMI P

Quick SortShweta Sahu

linear search and binary searchZia Ush Shamszaman

Algorithms Lecture 2: Analysis of Algorithms IMohamed Loey

B and B+ treeAshish Arun

Representation of binary tree in memoryRohini Shinde

daa-unit-3-greedy methodhodcsencet

Merge sort algorithmShubham Dwivedi

Strassen's matrix multiplicationMegha V

Brute force methodpriyankabhansali217

Graph coloring using backtrackingshashidharPapishetty

Merge sort algorithm power point presentationUniversity of Science and Technology Chitttagong

Quick Sort , Merge Sort , Heap SortMohammed Hussein

Binary Heap Tree, Data Structure Anand Ingle

Asymptotic notationDr Shashikant Athawale

Optimal binary search tree dynamic programmingP. Subathra Kishore, KAMARAJ College of Engineering and Technology, Madurai

Breadth First Search & Depth First SearchKevin Jadiya

Design and Analysis of AlgorithmsArvind Krishnaa

Data structures question paper anna universitysangeethajames07

Asymptotic NotationProtap Mondal

sparse matrix in data structureMAHALAKSHMI P

Quick SortShweta Sahu

linear search and binary searchZia Ush Shamszaman

Similar to Merge sort algorithm (20)

Brute Force and Divide & Conquer Techniquessusered62011

Daa chapter 2B.Kirron Reddi

Are there trends, changes in the mi.pptxpriyaaajadhav31

SWOT analysis is a strategic planning tool used to identify and evaluate the Strengths, Weaknesses, Opportunities, and Threats of a business, project, or individual. It helps in understanding both internal and external factors that can influence success. Here's what each component typically refers to: Strengths (Internal, Positive Factors): What does the organization or individual do well? What unique resources or advantages do they have? Examples: Strong brand reputation, skilled workforce, financial stability, proprietary technology. Weaknesses (Internal, Negative Factors): Where could the organization or individual improve? What factors hinder their success? Examples: Lack of resources, poor location, outdated technology, weak customer service. Opportunities (External, Positive Factors): What external factors could be leveraged for growth or success? Are there trends, changes in the market, or unmet needs that could be capitalized on? Examples: Market growth, changes in regulations, emerging technologies, changes in consumer preferences. Threats (External, Negative Factors): What external factors could challenge the success or growth? Are there competitors, market shifts, or other risks that could have a negative impact? Examples: Increased competition, economic downturns, regulatory changes, supply chain disruptions. Would you like to create a SWOT analysis for a specific project, business, or anything else? Let me know!

Sienna 4 divideandconquerchidabdu

Divide-and-conquer is an algorithm design technique that involves dividing a problem into smaller subproblems, solving the subproblems recursively, and combining the solutions. The document discusses several divide-and-conquer algorithms including mergesort, quicksort, and binary search. Mergesort divides an array in half, sorts each half, and then merges the halves. Quicksort picks a pivot element and partitions the array into elements less than and greater than the pivot. Both quicksort and mergesort have average-case time complexity of Θ(n log n).

Unit-2-Sorting (Merge+Quick+Heap+Binary Searach).pptsajalsinghal1512

Ada notesVIKAS SINGH BHADOURIA

This document provides an introduction to algorithms and data structures. It discusses algorithm design and analysis tools like Big O notation and recurrence relations. Selecting the smallest element from a list, sorting a list using selection sort and merge sort, and merging two sorted lists are used as examples. Key points made are that merge sort has better time complexity than selection sort, and any sorting algorithm requires at least O(n log n) comparisons. The document also introduces data structures like arrays and linked lists, and how the organization of data impacts algorithm performance.

Cs6402 design and analysis of algorithms may june 2016 answer keyappasami

The document discusses algorithms and complexity analysis. It provides Euclid's algorithm for computing greatest common divisor, compares the orders of growth of n(n-1)/2 and n^2, and describes the general strategy of divide and conquer methods. It also defines problems like the closest pair problem, single source shortest path problem, and assignment problem. Finally, it discusses topics like state space trees, the extreme point theorem, and lower bounds.

advanced algoTECHNICALGYANIBABUAA

This document presents an overview of the merge sort algorithm. It begins with an introduction explaining that merge sort is a divide and conquer algorithm that divides an input array in half, recursively sorts the halves, and then merges the sorted halves together. It then provides pseudocode for the merge sort algorithm, which works by recursively dividing the array in half until each subarray contains a single element, and then merging the sorted subarrays back together. Finally, it analyzes the time and space complexity of merge sort, concluding that it has time complexity of Θ(nlogn) and space complexity of Θ(n).

DYNAMIC PROGRAMMING AND GREEDY TECHNIQUEssusered62011

Divide and ConquerMelaku Bayih Demessie

Algorithm in computer scienceRiazul Islam

The document discusses divide and conquer algorithms. It explains that divide and conquer algorithms work by dividing problems into smaller subproblems, solving the subproblems independently, and then combining the solutions to solve the original problem. An example of finding the minimum and maximum elements in an array using divide and conquer is provided, with pseudocode. Advantages of divide and conquer algorithms include solving difficult problems and often finding efficient solutions.

Lecture 6 disjoint setAbirami A

The document discusses the disjoint set abstract data type (ADT). It can be used to represent equivalence relations and solve the dynamic equivalence problem. There are three main representations - array, linked list, and tree. The tree representation can be improved using two heuristics: smart union algorithm (e.g. union-by-rank) and path compression. Together these optimizations allow the disjoint set operations to run in near-linear time with respect to the total number of operations.

Algorithm Design Techiques, divide and conquerMinakshee Patil

Master of Computer Application (MCA) – Semester 4 MC0080Aravind NC

This document describes several sorting algorithms and asymptotic analysis techniques. It discusses bubble sort, selection sort, insertion sort, shell sort, heap sort, merge sort, and quick sort as sorting algorithms. It then explains asymptotic notation such as Big-O, Big-Omega, and Theta to describe the time complexity of algorithms. Finally, it asks questions about Fibonacci heaps, binomial heaps, Strassen's matrix multiplication algorithm, and formalizing a greedy algorithm.

376951072-3-Greedy-Method-new-ppt.pptRohitPaul71

The document discusses greedy algorithms and their use for optimization problems. It provides examples of using greedy approaches to solve scheduling and knapsack problems. Specifically, it describes how a greedy algorithm works by making locally optimal choices at each step in hopes of reaching a globally optimal solution. While greedy algorithms do not always find the true optimal, they often provide good approximations. The document also proves that certain greedy strategies, such as always selecting the item with the highest value to weight ratio for the knapsack problem, will find the true optimal solution.

Skiena algorithm 2007 lecture08 quicksortzukun

The document summarizes two sorting algorithms: Mergesort and Quicksort. Mergesort uses a divide and conquer approach, recursively splitting the list into halves and then merging the sorted halves. Quicksort uses a partitioning approach, choosing a pivot element and partitioning the list into elements less than and greater than the pivot. The average time complexity of Quicksort is O(n log n) while the worst case is O(n^2).

Disign and Analysis for algorithm in computer science and technologyritikkumarchaudhury7

ch03.pptxHebertNelsonQuionezO

This chapter discusses systems of two first order differential equations. It introduces linear systems with constant coefficients, which can be solved using eigenvalues and eigenvectors. The chapter presents methods to find the general solution of homogeneous systems and the solution satisfying initial conditions. Graphical approaches are described, including direction fields and phase portraits to visualize solutions. An example of a two-equation model of a rockbed heat storage system is provided and transformed into matrix notation.

Module 2_ Divide and Conquer Approach.pptxnikshaikh786

The document describes the divide and conquer approach and analyzes the complexity of several divide and conquer algorithms, including binary search, merge sort, quicksort, and finding minimum and maximum values. It explains the general divide and conquer method involves three steps: 1) divide the problem into subproblems, 2) solve the subproblems, and 3) combine the solutions to solve the original problem. It then provides detailed explanations and complexity analyses of specific divide and conquer algorithms.

Chapter 4.2 - ADTree_Divide_n_Conquer 2021g46179042

Brute Force and Divide & Conquer Techniquessusered62011

Daa chapter 2B.Kirron Reddi

Are there trends, changes in the mi.pptxpriyaaajadhav31

Sienna 4 divideandconquerchidabdu

Unit-2-Sorting (Merge+Quick+Heap+Binary Searach).pptsajalsinghal1512

Ada notesVIKAS SINGH BHADOURIA

Cs6402 design and analysis of algorithms may june 2016 answer keyappasami

advanced algoTECHNICALGYANIBABUAA

DYNAMIC PROGRAMMING AND GREEDY TECHNIQUEssusered62011

Divide and ConquerMelaku Bayih Demessie

Algorithm in computer scienceRiazul Islam

Lecture 6 disjoint setAbirami A

Algorithm Design Techiques, divide and conquerMinakshee Patil

Master of Computer Application (MCA) – Semester 4 MC0080Aravind NC

376951072-3-Greedy-Method-new-ppt.pptRohitPaul71

Skiena algorithm 2007 lecture08 quicksortzukun

Disign and Analysis for algorithm in computer science and technologyritikkumarchaudhury7

ch03.pptxHebertNelsonQuionezO

Module 2_ Divide and Conquer Approach.pptxnikshaikh786

Chapter 4.2 - ADTree_Divide_n_Conquer 2021g46179042

Recently uploaded (20)

David Boutry - Specializes In AWS, Microservices And Python.pdfDavid Boutry

With over eight years of experience, David Boutry specializes in AWS, microservices, and Python. As a Senior Software Engineer in New York, he spearheaded initiatives that reduced data processing times by 40%. His prior work in Seattle focused on optimizing e-commerce platforms, leading to a 25% sales increase. David is committed to mentoring junior developers and supporting nonprofit organizations through coding workshops and software development.

Machine Learning basics POWERPOINT PRESENETATIONDarrinBright1

Working with USDOT UTCs: From Conception to ImplementationAlabama Transportation Assistance Program

The TRB AJE35 RIIM Coordination and Collaboration Subcommittee has organized a series of webinars focused on building coordination, collaboration, and cooperation across multiple groups. All webinars have been recorded and copies of the recording, transcripts, and slides are below. These resources are open-access following creative commons licensing agreements. The files may be found, organized by webinar date, below. The committee co-chairs would welcome any suggestions for future webinars. The support of the AASHTO RAC Coordination and Collaboration Task Force, the Council of University Transportation Centers, and AUTRI’s Alabama Transportation Assistance Program is gratefully acknowledged. This webinar overviews proven methods for collaborating with USDOT University Transportation Centers (UTCs), emphasizing state departments of transportation and other stakeholders. It will cover partnerships at all UTC stages, from the Notice of Funding Opportunity (NOFO) release through proposal development, research and implementation. Successful USDOT UTC research, education, workforce development, and technology transfer best practices will be highlighted. Dr. Larry Rilett, Director of the Auburn University Transportation Research Institute will moderate. For more information, visit: https://aub.ie/trbwebinars

Water Industry Process Automation & Control Monthly May 2025Water Industry Process Automation & Control

Welcome to the May 2025 edition of WIPAC Monthly celebrating the 14th anniversary of the WIPAC Group and WIPAC monthly. In this edition along with the usual news from around the industry we have three great articles for your contemplation Firstly from Michael Dooley we have a feature article about ammonia ion selective electrodes and their online applications Secondly we have an article from myself which highlights the increasing amount of wastewater monitoring and asks "what is the overall" strategy or are we installing monitoring for the sake of monitoring Lastly we have an article on data as a service for resilient utility operations and how it can be used effectively.

ATAL 6 Days Online FDP Scheme Document 2025-26.pdfssuserda39791

introduction technology technology tec.pptxIftikhar70

twin tower attack 2001 new york cityharishreemavs

Mode-Wise Corridor Level Travel-Time Estimation Using Machine Learning ModelsJournal of Soft Computing in Civil Engineering

This research is oriented towards exploring mode-wise corridor level travel-time estimation using Machine learning techniques such as Artificial Neural Network (ANN) and Support Vector Machine (SVM). Authors have considered buses (equipped with in-vehicle GPS) as the probe vehicles and attempted to calculate the travel-time of other modes such as cars along a stretch of arterial roads. The proposed study considers various influential factors that affect travel time such as road geometry, traffic parameters, location information from the GPS receiver and other spatiotemporal parameters that affect the travel-time. The study used a segment modeling method for segregating the data based on identified bus stop locations. A k-fold cross-validation technique was used for determining the optimum model parameters to be used in the ANN and SVM models. The developed models were tested on a study corridor of 59.48 km stretch in Mumbai, India. The data for this study were collected for a period of five days (Monday-Friday) during the morning peak period (from 8.00 am to 11.00 am). Evaluation scores such as MAPE (mean absolute percentage error), MAD (mean absolute deviation) and RMSE (root mean square error) were used for testing the performance of the models. The MAPE values for ANN and SVM models are 11.65 and 10.78 respectively. The developed model is further statistically validated using the Kolmogorov-Smirnov test. The results obtained from these tests proved that the proposed model is statistically valid.

2.3 Genetically Modified Organisms (1).pptrakshaiya16

sss1.pptxsss1.pptxsss1.pptxsss1.pptxsss1.pptxajayrm685

Design Optimization of Reinforced Concrete Waffle Slab Using Genetic AlgorithmJournal of Soft Computing in Civil Engineering

This research presents the optimization techniques for reinforced concrete waffle slab design because the EC2 code cannot provide an efficient and optimum design. Waffle slab is mostly used where there is necessity to avoid column interfering the spaces or for a slab with large span or as an aesthetic purpose. Design optimization has been carried out here with MATLAB, using genetic algorithm. The objective function include the overall cost of reinforcement, concrete and formwork while the variables comprise of the depth of the rib including the topping thickness, rib width, and ribs spacing. The optimization constraints are the minimum and maximum areas of steel, flexural moment capacity, shear capacity and the geometry. The optimized cost and slab dimensions are obtained through genetic algorithm in MATLAB. The optimum steel ratio is 2.2% with minimum slab dimensions. The outcomes indicate that the design of reinforced concrete waffle slabs can be effectively carried out using the optimization process of genetic algorithm.

Generative AI & Large Language Models Agentsaasgharbee22seecs

How to Build a Desktop Weather Station Using ESP32 and E-ink DisplayCircuitDigest

seninarppt.pptx1bhjiikjhggghjykoirgjuyhhhjjAjijahamadKhaji

Nanometer Metal-Organic-Framework Literature ComparisonChris Harding

Autodesk Fusion 2025 Tutorial: User InterfaceAtif Razi

Uses of drones in civil construction.pdfsurajsen1729

Jacob Murphy Australia - Excels In Optimizing Software ApplicationsJacob Murphy Australia

In the world of technology, Jacob Murphy Australia stands out as a Junior Software Engineer with a passion for innovation. Holding a Bachelor of Science in Computer Science from Columbia University, Jacob's forte lies in software engineering and object-oriented programming. As a Freelance Software Engineer, he excels in optimizing software applications to deliver exceptional user experiences and operational efficiency. Jacob thrives in collaborative environments, actively engaging in design and code reviews to ensure top-notch solutions. With a diverse skill set encompassing Java, C++, Python, and Agile methodologies, Jacob is poised to be a valuable asset to any software development team.

Little Known Ways To 3 Best sites to Buy Linkedin Accounts.pdfgori42199

Modeling the Influence of Environmental Factors on Concrete Evaporation RateJournal of Soft Computing in Civil Engineering

Newly poured concrete opposing hot and windy conditions is considerably susceptible to plastic shrinkage cracking. Crack-free concrete structures are essential in ensuring high level of durability and functionality as cracks allow harmful instances or water to penetrate in the concrete resulting in structural damages, e.g. reinforcement corrosion or pressure application on the crack sides due to water freezing effect. Among other factors influencing plastic shrinkage, an important one is the concrete surface humidity evaporation rate. The evaporation rate is currently calculated in practice by using a quite complex Nomograph, a process rather tedious, time consuming and prone to inaccuracies. In response to such limitations, three analytical models for estimating the evaporation rate are developed and evaluated in this paper on the basis of the ACI 305R-10 Nomograph for “Hot Weather Concreting”. In this direction, several methods and techniques are employed including curve fitting via Genetic Algorithm optimization and Artificial Neural Networks techniques. The models are developed and tested upon datasets from two different countries and compared to the results of a previous similar study. The outcomes of this study indicate that such models can effectively re-develop the Nomograph output and estimate the concrete evaporation rate with high accuracy compared to typical curve-fitting statistical models or models from the literature. Among the proposed methods, the optimization via Genetic Algorithms, individually applied at each estimation process step, provides the best fitting result.

David Boutry - Specializes In AWS, Microservices And Python.pdfDavid Boutry

Machine Learning basics POWERPOINT PRESENETATIONDarrinBright1

Working with USDOT UTCs: From Conception to ImplementationAlabama Transportation Assistance Program

Water Industry Process Automation & Control Monthly May 2025Water Industry Process Automation & Control

ATAL 6 Days Online FDP Scheme Document 2025-26.pdfssuserda39791

introduction technology technology tec.pptxIftikhar70

twin tower attack 2001 new york cityharishreemavs

Mode-Wise Corridor Level Travel-Time Estimation Using Machine Learning ModelsJournal of Soft Computing in Civil Engineering

2.3 Genetically Modified Organisms (1).pptrakshaiya16

sss1.pptxsss1.pptxsss1.pptxsss1.pptxsss1.pptxajayrm685

Design Optimization of Reinforced Concrete Waffle Slab Using Genetic AlgorithmJournal of Soft Computing in Civil Engineering

Generative AI & Large Language Models Agentsaasgharbee22seecs

How to Build a Desktop Weather Station Using ESP32 and E-ink DisplayCircuitDigest

seninarppt.pptx1bhjiikjhggghjykoirgjuyhhhjjAjijahamadKhaji

Nanometer Metal-Organic-Framework Literature ComparisonChris Harding

Autodesk Fusion 2025 Tutorial: User InterfaceAtif Razi

Uses of drones in civil construction.pdfsurajsen1729

Jacob Murphy Australia - Excels In Optimizing Software ApplicationsJacob Murphy Australia

Little Known Ways To 3 Best sites to Buy Linkedin Accounts.pdfgori42199

Modeling the Influence of Environmental Factors on Concrete Evaporation RateJournal of Soft Computing in Civil Engineering

Merge sort algorithm

1. Prepared by:- Sruti sen patra Merge sort

2. Definition:- Merge sort is one of the most efficient sorting algorithms. It works on the principle of Divide and Conquer. Merge sort repeatedly breaks down a list into several sub lists until each sub list consists of a single element and merging those sub lists in a manner that results into a sorted list. Divide and conquer rule:- A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.

3. Algorithm(divide) Mergesort(A, lb , ub,) { If(lb < ub) { Mid = lb+ub/2 Mergesort (A,lb,mid); Mergesort (A,mid+1,ub); Merge (A,lb,mid,ub) } }

4. Algorithm(Merge) Mergesort( A, lb , mid , ub) { i=lb; J=mid +1; K= lb; While ( i<=mid && j<=ub) { If(a[i]<=a[j]) { b[k]=a[i] i++;

5. Algorithm(merge) } Else b[k]=a[j] ; J++; } K++; }} If(i>mid) { while (j< =ub) B[k]=a[j]; J++; K++;

6. Algorithm(merge) } Else { While (i<=mid) B[k]=a[i]; i++; K++; } } For(k=lb; k <=ub ; k++) { a[k]= b[k]; }}

7. Time complexity:- Merge Sort is a recursive algorithm and time complexity can be expressed as following recurrence relation. T(n) = 2T(n/2) + n  Recurrence tree method:- Recursion Tree is another method for solving the recurrence relations. A recursion tree is a tree where each node represents the cost of a certain recursive sub-problem. We sum up the values in each node to get the cost of the entire algorithm.

10. The solution of the above recurrence is O(nLogn). The list of size N is divided into a max of Logn parts, and the merging of all sublists into a single list takes O(N) time, the worst-case run time of this algorithm is O(nLogn) Best Case Time Complexity: O(n*log n) Worst Case Time Complexity: O(n*log n) Average Time Complexity: O(n*log n) The time complexity of MergeSort is O(n*Log n) in all the 3 cases (worst, average and best) as the mergesort always divides the array into two halves and takes linear time to merge two halves.

Merge sort algorithm

Recommended

More Related Content

What's hot (20)

Similar to Merge sort algorithm (20)

Recently uploaded (20)

Merge sort algorithm