Merge Sort in Golang with Examples

swirl

The post Merge Sort in Golang with Examples first appeared on Qvault.

Merge sort is a recursive sorting algorithm and, luckily for us, it’s quite a bit faster than bubble sort. Merge sort is a divide 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

Sorry to interrupt! I just wanted to mention that you should check out my new free Go course. It’s designed to teach you all the fundamentals of my favorite coding language.

Learn Golang Now

Full example of the merge sort algorithm

Merge sort actually has two functions involved, the recursive mergeSort function, and the merge function.

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



func mergeSort(items []int) []int {     if len(items) < 2 {         return items     }     first := mergeSort(items[:len(items)/2])     second := mergeSort(items[len(items)/2:])     return merge(first, second) }


Code language: HTML, XML (xml)


The merge() 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.




func merge(a []int, b []int) []int {     final := []int{}     i := 0     j := 0     for i < len(a) && j < len(b) {         if a[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])     }     return final }


Code language: PHP (php)


Using the algorithm in code




func main() { 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] }


Code language: JavaScript (javascript)


Why use merge sort?


Pros


    

  • Fast. Merge sort is much faster than bubble sort, being O(n*log(n)) instead of O(n^2).
    • 

  • Stable. Merge sort is also a stable 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 recommend not reinventing the wheel and using the built-in sort.Sort method.


Merge sort Big-O complexity


Merge sort has a complexity of O(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.






Thanks for reading, now take a course!


Interested in a high-paying job in tech? Land interviews and pass them with flying colors after taking my hands-on coding courses.




Start coding now




Questions?


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 to let me know so I can get it corrected!


Subscribe to my newsletter for more coding articles delivered straight to your inbox.









source https://qvault.io/golang/merge-sort-golang/






































Comments











Post a Comment























Popular posts from this blog









Why is Exclusive Or (XOR) Important in Cryptography?




















Image







    If you are getting into cryptography, or just trying to understand the fundamentals, you may have noticed that the exclusive-or operation is used quite often, especially in ciphers.  What is XOR ( ⊕ )?  XOR, or “exclusive or” operates on binary data. It returns true if both of its inputs are opposites (one false and one true), otherwise, it returns false.     An example in go code would be something like:  func exclusiveOr(a bool, b bool) bool {         return a != b }  XOR Cipher – The Perfect Cipher  The XOR operation can be used as a simple cipher for encrypting and decrypting messages with a single key. This is known as symmetric encryption.  It is interesting to note that if:   The key is the same size as the message  The key is kept secret and generated truly randomly   Then the cipher is impossible  to crack. This is known as a one time pad . However, a simple XOR shouldn’t be used in production due to the key length needing to be too long to be practical.  Cipher Example  A...








Read more










Base64 vs Base58 Encoding




















Image







 By Lane Wagner –  @wagslane  on Twitter   Base64 is one of the most popular encoding formats for representing data. Have some binary data? Base64 encode it for convenient readability and parsing. Base58 is just another encoding format (with 58 characters instead of 64, and has gained popularity largely due to Bitcoin and other cryptocurrencies.  When it comes to data encoding, there is typically a trade-off made between:   Human Readability: Do humans have a good idea of what is being represented at a glance?  Efficient data compression: How many bytes are used to represent the same data?   Let’s rank Base58, Base64, and ASCII encoding against each other using these metrics!  First: A Note on Binary  All data is stored in a raw binary format on computers. These encoding formats (Base64, Base58, and ASCII) are just different ways of reading and writing binary data. For example, in Base64 the binary code 000000  represents the letter A , but in ASCII the binary 00000000  repres...








Read more










(Very) Basic Intro to Hash Functions (SHA-256, MD-5, etc)




















Image







 This is going to be a basic introduction to hash functions. I will assume most of my audience is here to gain an understanding of why hash functions are used and the basic idea of why they work. My goal is to explain it in a general sense, I will be omitting proofs and implementation details and instead focusing on the high-level principles.     Why Use A Hash Function?  Hash functions are used all over the internet in order to securely store passwords, find duplicate records, quickly store and retrieve data, and more. For example,  Qvault  uses hashes to extend master passwords into private encryption keys.  A longer list of uses here:  https://en.wikipedia.org/wiki/Hash_function#Uses  I want to focus on several important features of hash functions, arguably the most important features.   Hash functions scramble data deterministically  No matter the input, the output of a hash function always has the same size  The original data can not be retrieved from the scrambled d...








Read more