Live Chat & Podcast at 1:00PM Eastern on Sunday!
There's no such thing as a stupid question, but they're the easiest to answer.
JoinTour
Login
Search
Software Development
Tag Cloud
access acer asus bios bsod computer crash desktop driver drivers error ethernet excel freeze gaming hard drive hardware hdmi internet laptop malware memory modem monitor motherboard mouse network printer problem ram registry repair router slow software sound trojan ubuntu 11.10 uninstall usb video virus vista wifi windows windows 7 windows 7 32 bit windows 7 64 bit windows xp wireless
Search
Search for:
Tech Support Guy Forums > Software & Hardware > Software Development >
Merge Sort

Reply  
Thread Tools
Daskill's Avatar
Member with 260 posts.
 
Join Date: Oct 2007
Experience: Intermediate
30-Nov-2008, 12:53 PM #1
Merge Sort
I'm having trouble understanding merge sort. Can anyone explain it to me?
-Fabez-'s Avatar
Senior Member with 1,943 posts.
 
Join Date: Jul 2008
Location: Earth
Experience: General
01-Dec-2008, 05:22 PM #2
http://www.cprogramming.com/tutorial...mergesort.html Explains how it works in C, I have never used a merge sort, but it is explained clearly in the webpage and should be generic for all programming languages.
Daskill's Avatar
Member with 260 posts.
 
Join Date: Oct 2007
Experience: Intermediate
02-Dec-2008, 06:39 AM #3
I'm a little confused, what does it mean if it is O(nlog(n)) complexity?

Also, if I am sorting by merge sort and have a group of three values I have to split up, do I split it up so I have the single value first, then the two values, or do I do it the other way round?

So if I've got (13, 6, 7), does it then become

(13), (6,7)

or

(13,6), (7)

?

Last edited by Daskill; 02-Dec-2008 at 07:27 AM..
BrutalB's Avatar
Junior Member with 7 posts.
 
Join Date: Nov 2008
Location: Standerton, South Africa
03-Dec-2008, 02:42 PM #4
O(nlog(n)) is the running time of the algorithm... Merge sorting is a very efficient way of sorting (compare the Big Oh values to other sorting algorithms)... And as far as I know, it doesn't matter which way round you go with the 13, 6 and 7 or 13 and 6, 7...

Any corrections are welcome, that's what I remember from my Datastructures and Algorithms classes
BobFoster's Avatar
Junior Member with 18 posts.
 
Join Date: Dec 2008
Experience: Advanced
05-Dec-2008, 01:11 PM #5
The two halves of the sort are treated identically, so it doesn't matter which half has the more entries if you have an odd number of elements to sort. You only need lists of similar length anyway when splitting; the exact number of elements is not actually important.

O(n log n) is an indication of the efficiency of the algorithm, as BrtualB has already said. Specifically, n refers to the number of items in the list you're sorting and O(50) would mean the sort takes 50 steps to complete. The O() value is often called the complexity.

Sorting algorithms can usually be classified with an average and worst case complexity and Merge Sort has O(n log n) for both average and worst. If you compare this with other common algorithms: Quicksort, O(n log n) average but O(n^2) worst case and Bubble sort, O(n^2) in both cases, you can see that of the three it is the best. Work out a few O values for large numbers of items and you'll see exactly how much more efficient it is than a bubble sort, for example.

Hope this makes sense.

Regards,
Bob

Last edited by BobFoster; 05-Dec-2008 at 01:25 PM.. Reason: Typo
Reply

THIS THREAD HAS EXPIRED.
Are you having the same problem? We have volunteers ready to answer your question, but first you'll have to join for free. Need help getting started? Check out our Welcome Guide.

Search Tech Support Guy

Find the solution to your
computer problem!




Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
WELCOME TO TECH SUPPORT GUY! Are you looking for the solution to your computer problem? Join our site today to ask your question -- for free! Our site is run completely by volunteers who want to help you solve your computer problems. See our Welcome Guide to get started.
Thread Tools



Facebook Facebook Twitter Twitter TechGuy.tv TechGuy.tv Mobile TSG Mobile
You Are Using:
Server ID
Advertisements do not imply our endorsement of that product or service.
All times are GMT -4. The time now is 12:32 AM.
Copyright © 1996 - 2011 TechGuy, Inc. All rights reserved.

Powered by Cermak Technologies, Inc.