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]