For a better understanding of this example, we always recommend you to learn the basic topics of Golang programming listed below:
There are so many ways to implement sorting data. Whenever we compare the efficiency and speed of each sorting algorithm, some of them are more or less efficient and faster than others. While we compare the sorting jobs, we can say there is no best all-in-one solution that works the greatest for all the cases. That means each algorithm has its own importance. In this section, we’ll focus our attention on Merge Sorting Algorithm.
Merge sort is one of the classic sorting algorithms which works based on the divide & conquer strategy, which means that we split our problem into smaller chunks, which will help you to make it easier to solve.
The basic idea of merge sort is to splits the input array into two sub-arrays. Solves each individual sub-array by recursive process, and then at the end, we merge the two sorted arrays as a final sorted array. We can say Merge sort is much faster than bubble sort. Note that, the time complexity of Merge Sort is θ(nLogn) in all 3 cases (worst, average and best).
Let’s understand the implementation of the Merge sort.
In this GO program, we are importing the “fmt” package to include some standard libraries into the program. We accept the user's values using the fmt.scanln() and fmt.println() methods which are defined under the fmt package. In order to use these functions, we need to import the “fmt” package. After that Main function starts, inside the main, we are doing the whole program.
In this Go program, we are using mainly two functions, the recursive mergeSort function, and the merge function.
the mergeSort function is a recursive function that calls itself twice to split the array into two roughly equal parts, then call merge() to fit those sub-arrays back together like a sorted array.
STEP 1: Import the package fmt
STEP 2: Open the main() to start the program, GO program execution starts with the main()
STEP 3: Declare the variable n.
STEP 4: Read the size of the array as n
STEP 5: Define the array A[]
STEP 6: Read the A[] array elements by using a 'for loop'.
STEP 7: Perform Merge sort by calling function mergeSort(A).
STEP 8: Use for loop to display sorted array.
STEP 9: Exit
STEP 1: check using if the length of the unsorted array A is less than 2. If so, return array A.
STEP 2: Assign return value of mergeSort(A[:len(items)/2]) into a variable first.
STEP 3: Assign return value of mergeSort(A[len(items)/2:]) into a variable second.
STEP 4: Do merging of two sorted lists back into a single sorted list by calling function merge(first, second).
STEP 5: Return resulting array into the main function
STEP1: Assign the first and second array into a[] and b[] respectively as function parameters.
STEP 2: Declare an array final and loop variables i and j.
STEP 3: Assign i=0 and j=0.
STEP 4: Iterate as many times as the smallest length of the 2 arrays/slices.
STEP 5: On each iteration, we compare the elements of left & right sides, i.e. a[i] and b[i], by using a loop and inserting the smaller ones in the resulting array final, till we run out of iterations.
STEP 6: Insert all the missing elements, when we run out of iterations. Like the case when one sub-array has the smaller elements, the other sub-array will have elements we have not inserted in the resulting array final.
STEP 7: Return resulting array final.
package main
import "fmt"
func main() {
fmt.Println("Enter the size of the array")
var n int
fmt.Scan(&n)
A := make([]int, n, 100)
fmt.Println("Enter elements of the array : ")
for i := 0; i < n; i++ {
fmt.Scan(&A[i])
}
fmt.Println("Sorted array:")
fmt.Println(mergeSort(A))
}
func mergeSort(A []int) []int {
if len(A) < 2 {
return A
}
first := mergeSort(A[:len(A)/2])
second := mergeSort(A[len(A)/2:])
return merge(first, second)
}
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
}
Enter the size of the array 5 Enter elements of the array : 3 8 2 6 1 Sorted array: [1 2 3 6 8]
