Movatterモバイル変換


[0]ホーム

URL:


Skip to content
DEV Community
Log in Create account

DEV Community

Boot.dev profile imageLane Wagner
Lane Wagner forBoot.dev

Posted on • Originally published atqvault.io on

     

Merge Sort in Golang with Examples

swirl

The postMerge Sort in Golang with Examples first appeared onQvault.

Merge sort is a recursive sorting algorithm and, luckily for us, it’s quite a bit faster thanbubble sort. Merge sort is adivide and conquer algorithm.

Divide

  • Divide the input slice into two (equal) halves
  • Recursively sort the two halves

Conquer

  • Merge the two halves to form a sorted array

merge sort gif

Full example of the merge sort algorithm

Merge sort actually has two functions involved, the recursivemergeSort function, and themerge function.

Let’s write themergeSort() function first. It’s a recursive function, which means it calls itself, and in this case, it actually calls itselftwice. The point of themergeSort function is to split the array into two roughly equal parts, call itself on those parts, then callmerge() to fit those halves back together.

funcmergeSort(items[]int)[]int{iflen(items)<2{returnitems}first:=mergeSort(items[:len(items)/2])second:=mergeSort(items[len(items)/2:])returnmerge(first,second)}<smallid="shcb-language-1"><span>Codelanguage:</span><span>Go</span><span>(</span><span>go</span><span>)</span></small>
Enter fullscreen modeExit fullscreen mode

Themerge() function is used for merging two sorted lists back into a single sorted list, its where the “magic” really happens. At the lowest level of recursion, the two “sorted” lists will each have a length of 1. Those single element lists will be merged into a sorted list of length two, and we can build of from there.

funcmerge(a[]int,b[]int)[]int{final:=[]int{}i:=0j:=0fori<len(a)&&j<len(b){ifa[i]<b[j]{final=append(final,a[i])i++}else{final=append(final,b[j])j++}}for;i<len(a);i++{final=append(final,a[i])}for;j<len(b);j++{final=append(final,b[j])}returnfinal}<smallid="shcb-language-2"><span>Codelanguage:</span><span>Go</span><span>(</span><span>go</span><span>)</span></small>
Enter fullscreen modeExit fullscreen mode

Using the algorithm in code

funcmain(){unsorted:=[]int{10,6,2,1,5,8,3,4,7,9}sorted:=mergeSort(unsortedInput)// sorted = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]}<smallid="shcb-language-3"><span>Codelanguage:</span><span>Go</span><span>(</span><span>go</span><span>)</span></small>
Enter fullscreen modeExit fullscreen mode

Why use merge sort?

Pros

  • Fast. Merge sort is much faster than bubble sort, beingO(n*log(n)) instead ofO(n^2).
  • Stable. Merge sort is also astable sort which means that values with duplicate keys in the original list will be in the same order in the sorted list.

Cons

  • Extra memory. Most sorting algorithms can be performed using a single copy of the original array. Merge sort requires an extra array in memory to merge the sorted subarrays.
  • Recursive: Merge sort requires many recursive function calls, and function calls can have significant resource overhead.

If you need a sorting algorithm to use in a production system, I recommendnot reinventing the wheel and using the built-in sort.Sort method.

Merge sort Big-O complexity

Merge sort has a complexity ofO(n*log(n)). Don’t be fooled because there aren’t an explicit number of for-loops to count in the code. In merge sort’s case, the number of recursive function calls is important.

Ready to take action and get coding?

Try out our coding courses for free

Join our Discord community

Have questions or feedback?

Follow and hit me up on Twitter@q_vault if you have any questions or comments. If I’ve made a mistake in the article be sure tolet me know so I can get it corrected!

Top comments(1)

Subscribe
pic
Create template

Templates let you quickly answer FAQs or store snippets for re-use.

Dismiss
CollapseExpand
 
jamespatterson profile image
James Patterson
  • Joined

Informative information about merge sort coding algorithm that is quite useful. I’m sure the various fresh developers are getting help about fixing and understanding the problems. Thumbs up and continue to bring onresumehelpaustralia.com/it-cv-writ... related updates these are wise.

Are you sure you want to hide this comment? It will become hidden in your post, but will still be visible via the comment'spermalink.

For further actions, you may consider blocking this person and/orreporting abuse

Learn deeper. Build more. Get hired.

Learn modern back-end development

More fromBoot.dev

DEV Community

We're a place where coders share, stay up-to-date and grow their careers.

Log in Create account

[8]ページ先頭

©2009-2025 Movatter.jp