## Merge Sort real life example.(39/02 intake cse)

Write down the real-life example of merge sort.

(the real life example of insertion sort is sorting playing cards ).

Lost your password? Please enter your email address. You will receive a link and will create a new password via email.

## Comments ( 14 )

Id:17183103053

Merge sort is a sorting algorithm, which is commonly used in computer science.It is divide, combine and conqure algorithm

A real life case for a mergesort might be this scenario _

suppose,overnight your office was totally trasted by some thieves or such and all your numerous file cabinets of folders and contents strewn every where. It is now 9 a.m. the auditors are deo at 11 a.m. for a crucial inspection.

You must have all these file back in takck by 11.

You run down the hall and get every one you can find to come and sort big similar size file into alphabetical order so that you can MERGE the files back into how they were when you turned of the lights last night.

Distribution processing like martin puryear mentioned.

#mergesort

ID:17183103077

There are many real life example of merge sort.Such as-

1.playing card.

2.Playing chess etc.

Step 1:

Divide by finding the number q of the position midway,q=6.Do this step the some way we found the midpoint in binary search,divide by 2 and round down.

Step 2:

The conquer step had us sort the two subarray array[0…6] which contains [5,6,7,2,4,3,Q] and array[7…12] which contains[10,j,8,k,9,A].when we come back from the conquer step, each of the two subarray is sorted,array[0…6] contains[2,3,4,5,6,7,Q] and array [7…12] contains [8,9,10,j,k,A]. So that the full array is [2,3,4,5,6,7,Q,8,9,10,j,k,A].

Step 3:

Finally, the combine step merge the two sorted subarray in the first half and the second half,producing the final sorted array [2,3,4,5,6,7,8,9,10,j,Q,k,A].

id: 17183103068

Merge sort is one of the most efficient sorting algorithms. It works on the principle of Divide and Conquer.

real-life example of merge sort-

I have two sets of graded papers from the same class and both sets are alphabetized. If I want to merge the two piles into one, I don’t have to start all over again, I can use the work that’s already been down alphabetizing them separately. The first paper on the merged list has to be either the top paper from list #1 or the top from list #2. I take that paper and put it on a new stack face down. Now I make the comparison between the new two papers on top of the stacks and put it face down on the new stack, again and again, until all the papers are on the new stack face down. Once one of the original stacks is depleted, there are no more comparisons to be made and I can put the rest of the remaining stack face down on top of the merged stack, turn it back face up and it is completely sorted.

A real life case for a mergesort might be this scenario _

suppose,overnight your office was totally trasted by some thieves or such and all your numerous file cabinets of folders and contents strewn every where. It is now 9 a.m. the auditors are deo at 11 a.m. for a crucial inspection.

You must have all these file back in takck by 11.

You run down the hall and get every one you can find to come and sort big similar size file into alphabetical order so that you can MERGE the files back into how they were when you turned of the lights last night.

Distribution processing like martin puryear mentioned.

ID 17183103052

In sorting n objects, merge sort has an average and

worst-case performance of O ( n log n ). If the running time of merge sort for a list of length n is T ( n ), then the recurrence T ( n ) = 2 T( n /2) + n follows from the definition of the algorithm (apply the algorithm to two lists of half the size of the original list, and add the n steps taken to merge the resulting two lists). The closed form follows from the master theorem for divide-and-conquer recurrences .

In the worst case, the number of comparisons merge sort makes is given by the sorting numbers . These numbers are equal to or slightly smaller than ( n ⌈ lg n ⌉ − 2 ⌈lg n ⌉ + 1), which is between ( n lg n − n + 1) and ( n lg n + n + O(lg n )). [5]

For large n and a randomly ordered input list, merge sort’s expected (average) number of comparisons approaches α ·n fewer than the worst case where

In the worst case, merge sort does about 39% fewer comparisons than quicksort does in the average case. In terms of moves, merge sort’s worst case complexity is O ( n log n )—the same complexity as quicksort’s best case, and merge sort’s best case takes about half as many iterations as the worst case. [ citation needed ]

Merge sort is more efficient than quicksort for some types of lists if the data to be sorted can only be efficiently accessed sequentially, and is thus popular in languages such as Lisp , where sequentially accessed data structures are very common. Unlike some (efficient) implementations of quicksort, merge sort is a stable sort.

Merge sort’s most common implementation does not sort in place; [6] therefore, the memory size of the input must be allocated for the sorted output to be store..

ID 17183103047

In sorting n objects, merge sort has an average and

worst-case performance of O ( n log n ). If the running time of merge sort for a list of length n is T ( n ), then the recurrence T ( n ) = 2 T( n /2) + n follows from the definition of the algorithm (apply the algorithm to two lists of half the size of the original list, and add the n steps taken to merge the resulting two lists). The closed form follows from the master theorem for divide-and-conquer recurrences .

In the worst case, the number of comparisons merge sort makes is given by the sorting numbers . These numbers are equal to or slightly smaller than ( n ⌈ lg n ⌉ − 2 ⌈lg n ⌉ + 1), which is between ( n lg n − n + 1) and ( n lg n + n + O(lg n )). [5]

For large n and a randomly ordered input list, merge sort’s expected (average) number of comparisons approaches α ·n fewer than the worst case where

In the worst case, merge sort does about 39% fewer comparisons than quicksort does in the average case. In terms of moves, merge sort’s worst case complexity is O ( n log n )—the same complexity as quicksort’s best case, and merge sort’s best case takes about half as many iterations as the worst case. [ citation needed ]

Merge sort is more efficient than quicksort for some types of lists if the data to be sorted can only be efficiently accessed sequentially, and is thus popular in languages such as Lisp , where sequentially accessed data structures are very common. Unlike some (efficient) implementations of quicksort, merge sort is a stable sort.

Merge sort’s most common implementation does not sort in place; [6] therefore, the memory size of the input must be allocated for the sorted output to be stored.

Id : 17183103060

Real life example of merge sort

Answer : E-commerce website/platform

Description : Most of us might see a section in various e-commerce website ”You might like” in which we found some stuff of our favourit! Do you know how it actually work?

E-commerce websitemaintains an array of it’s all users with their activities on the website and when the have some latest products in their latest products list which also another array the devide those product in array according to user’s array of choice

Another mega example of using merge sorting is two of india’s biggest e-commerce website policybazar.com and trivago.com who use merge sorting for creating best price and stuff for it’s users.

Id:171873103066

Question: The real life example of marge sort

solution:

Marge sorts of patterns are a bit tricky in real life. In nice easy computer-science land, every step is the same, just smaller. Merge sort is clearly the ultimate easy example of this.

In real life….

1. If you want to divide a long loaf of bread in 8 or 16 equal pieces, generally people cut it into two equal halves first and then cut each half into two equal halves again, repeating the process until you get as many pieces as you want – 8, 16, 32, or whatever. Almost nobody tries to divide the loaf into 8 pieces all at once – people can guess halves much better than eighths.

Or,

we tend to break things up along useful lines. If we’re sorting change, we first divide the coins up by denominations, then total up each denomination before adding them together. When we put together a puzzle, we divide out the edge pieces first, put them together, then build the rest of the puzzle on that. In war, we divide an opponent into pieces which cannot work as a cohesive unit, then crush them.

We see this in real life more often than blind divisions because we, as humans, know we can divide along useful lines. The closest I know of that is quick sort’s attempt to find a middle index to partition with.

One thing I find tricky about these divide and conquer algorithms is that they

looklike an infinite regression. You keep proving you can sort lists as long as you can sort smaller lists…. which you know you can do because you can sort smaller lists… so on and so forth. Infinite regression is a serious faux pas in modern logic, so I think people may get confused by that. Showing that “if I can sort a list of length n, I can sort a list of length 2n” would be the more traditional mathematical induction approach.Then again, all may be for naught, for it is quite clear the best use for divide an conquer in real life is to put together a thrilling huungrian dance.

Id: 17183103049

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 sublists until each sublist consists of a single element and merging those sublists in a manner that results into a sorted list.

## A merge sort works as follows:

## Top-down Merge Sort Implementation:

The top-down merge sort approach is the methodology which uses recursion mechanism. It starts at the Top and proceeds downwards, with each recursive turn asking the same question such as “What is required to be done to sort the array?” and having the answer as, “split the array into two, make a recursive call, and merge the results.”, until one gets to the bottom of the array-tree.

Example: Let us consider an example to understand the approach better.

Top-down Implementation

## Merging of two lists done as follows:

The first element of both lists is compared. If sorting in ascending order, the smaller element among two becomes a new element of the sorted list. This procedure is repeated until both the smaller sublists are empty and the newly combined sublist covers all the elements of both the sublists.

Merging of two lists

## Implementation Of Merge Sort

## Bottom-Up Merge Sort Implementation:

The Bottom-Up merge sort approach uses iterative methodology. It starts with the “single-element” array, and combines two adjacent elements and also sorting the two at the same time. The combined-sorted arrays are again combined and sorted with each other until one single unit of sorted array is achieved.

ID :17183103061

Question :Real life example of merge sort .

solution :

Merge Sort is a sorting algorithm, which is commonly used in computer science. Merge Sort is a divide and conquer algorithm. It works by recursively breaking 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. So Merge Sort first divides the array into equal halves and then combines them in a sorted manner.

## Merge Sort Algorithms: Steps on how it works:

Below is an image of an array, which needs to be sorted. We will use Merge Sort Algorithm, to sort this array:

Id:- 17183103076

Real life example of merge sort.

Solution:-

I had 25 years of stock market tick data in 300 files. I wanted to combine the files and remove duplicate data. Some of the files were not properly sorted by time. Each file was about 150MB, so I could not load all of the data into RAM at once. I only have 32GB of ram. I could use virtual memory, but it would cause lots of swapping and bring the system to its knees. Merge sort was the answer. Actually I first sorted each file individually using in-memory quicksort and then recursively merged them pairwise, removing duplicates with each merge. Done in a few seconds. Not strictly a merge sort, but based on the same concept.

Id:17183103070

intake:39/2

An

exampleofmerge sort. First divide the list into the smallest unit (1 element), then compare each element with the adjacent list tosortandmergethe two adjacent lists. In computer science,merge sort(also commonly spelledmergesort) is an efficient, general-purpose, comparison-basedsortingalgorithm.Id:17183103074

Merge sort is a sorting algorithm, which is commonly used in computer science.It is divide, combine and conqure algorithm

A real life case for a mergesort might be this scenario _

suppose,overnight your office was totally trasted by some thieves or such and all your numerous file cabinets of folders and contents strewn every where. It is now 9 a.m. the auditors are deo at 11 a.m. for a crucial inspection.

You must have all these file back in takck by 11.

You run down the hall and get every one you can find to come and sort big similar size file into alphabetical order so that you can MERGE the files back into how they were when you turned of the lights last night.

Distribution processing like martin puryear mentioned.

ID : 17183103056

Question: The real life example of marge sort

solution:

Marge sorts of patterns are a bit tricky in real life. In nice easy computer-science land, every step is the same, just smaller. Merge sort is clearly the ultimate easy example of this.

In real life….

1. If you want to divide a long loaf of bread in 8 or 16 equal pieces, generally people cut it into two equal halves first and then cut each half into two equal halves again, repeating the process until you get as many pieces as you want – 8, 16, 32, or whatever. Almost nobody tries to divide the loaf into 8 pieces all at once – people can guess halves much better than eighths.

Or,

we tend to break things up along useful lines. If we’re sorting change, we first divide the coins up by denominations, then total up each denomination before adding them together. When we put together a puzzle, we divide out the edge pieces first, put them together, then build the rest of the puzzle on that. In war, we divide an opponent into pieces which cannot work as a cohesive unit, then crush them.

We see this in real life more often than blind divisions because we, as humans, know we can divide along useful lines. The closest I know of that is quick sort’s attempt to find a middle index to partition with.

One thing I find tricky about these divide and conquer algorithms is that they

looklike an infinite regression. You keep proving you can sort lists as long as you can sort smaller lists…. which you know you can do because you can sort smaller lists… so on and so forth. Infinite regression is a serious faux pas in modern logic, so I think people may get confused by that. Showing that “if I can sort a list of length n, I can sort a list of length 2n” would be the more traditional mathematical induction approach.Then again, all may be for naught, for it is quite clear the best use for divide an conquer in real life is to put together a thrilling huungrian dance.