← Posts

# Merge Sort in Go and Javascript

#### 1 dayago

###### 25/05/2019

Here's my implementation of the Mergesort algorithm in Golang

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
``````package main

import (
"fmt"
"io/ioutil"
"math/rand"
"strconv"
"strings"
"time"
)

func main() {
start := time.Now()
arr := randArr(20)
// Merge sort array
fmt.Println("\n Sorted \n", mergeSort(arr))
fmt.Println("Sorted in: ", time.Since(start))
}

// Function to generate random array
func randArr(size int) []int {
arr := make([]int, size, size)
rand.Seed(time.Now().UnixNano())
for i := 0; i < size; i++ {
arr[i] = rand.Intn(99)
}
return arr
}

// Merge sort accepts an array and recursively sorts it
func mergeSort(arr []int) []int {
if len(arr) < 2 {
return arr
}
middle := (len(arr)) / 2
return merge(mergeSort(arr[:middle]), mergeSort(arr[middle:]))
}

// Merges two arrays into one
func merge(left, right []int) []int {
var sortedArr []int
// Check for inversions while array
for len(left) > 0 && len(right) > 0 {
if left[0] <= right[0] {
sortedArr = append(sortedArr, left[0])
left = left[1:] // Just like shift(), remove first and return slice
} else {
sortedArr = append(sortedArr, right[0])
right = right[1:] // Just like shift(), remove first and return slice
}
}

// Append to sortedArr if no inversions and
for len(left) > 0 {
sortedArr = append(sortedArr, left[0])
left = left[1:] // Just like shift(), remove first and return slice
}
for len(right) > 0 {
sortedArr = append(sortedArr, right[0])
right = right[1:] // Just like shift(), remove first and return slice
}
return sortedArr
}``````

and in Javascript

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
``````'use strict'
const fs = require('fs');
const filename = process.argv[2];

if (err) throw err;
const array = data.split('\n');
console.log(mergeSort(array))
});

function mergeSort(arr){
// Base case
let arrLength = arr.length
if(arrLength <= 1){
return arr
}
// Split arrays in halves
let middle = Math.floor(arrLength / 2)
let left = arr.slice(0, middle)
let right = arr.slice(middle, arrLength)

// Sort two halves of split array
let leftSorted = mergeSort(left)
let rightSorted = mergeSort(right)
return merge(leftSorted, rightSorted)
}

function merge(left, right){
let sortedArr = [];
// In case of arrays not size of 1
while(left.length && right.length){
if(parseInt(left[0]) <= parseInt(right[0])){
sortedArr.push(left.shift())
} else {
sortedArr.push(right.shift())
}
}
// If array still has elements, we concatenate
// them to the sorted array, since already sorted
if (left.length){
sortedArr = sortedArr.concat(left)
}
if (right.length){
sortedArr = sortedArr.concat(right)
}
return sortedArr
}``````