Skip to content

Instantly share code, notes, and snippets.

@AlanD20
Last active May 2, 2022 11:16
Show Gist options
  • Save AlanD20/b5d8efc631e70fa3f5182cb769e85b80 to your computer and use it in GitHub Desktop.
Save AlanD20/b5d8efc631e70fa3f5182cb769e85b80 to your computer and use it in GitHub Desktop.
Merge sort algorithm in javascript / python
// Testing Example
const list = [5, 2, 1, 4, 5, 2, 5, 7, 9, 8, 3]
console.log("Before Merge Sorting:");
console.log(...list);
mergeSort(list);
console.log("After Merge Sorting:");
console.log(...list);
function mergeSort(list) {
const size = list.length
if (size <= 1) return;
// Get left size
const leftSize = Math.ceil(size / 2)
// * in Other languages, You may need right list size
// ? const rightSize = size - leftSize
const left = splitList(list, 0, leftSize)
const right = splitList(list, leftSize, size)
// Destructure into single array using Recursion
mergeSort(left)
mergeSort(right)
// merge
merge(list, left, right)
}
function merge(list, left, right) {
const leftSize = left.length;
const rightSize = right.length;
// Three pointers for left, right, current list
let leftP = 0;
let rightP = 0;
let primaryP = 0
while (leftP < leftSize && rightP < rightSize) {
if (left[leftP] <= right[rightP]) {
list[primaryP] = left[leftP]
leftP++
} else {
list[primaryP] = right[rightP]
rightP++
}
primaryP++
}
// Add left over in left list
while (leftP < leftSize) {
list[primaryP] = left[leftP]
leftP++
primaryP++
}
// Add left over in right list
while (rightP < rightSize) {
list[primaryP] = right[rightP]
rightP++
primaryP++
}
}
function splitList(list, start, end) {
const newList = [];
for (let i = start; i < end; i++) newList.push(list[i])
return newList
}
import math
def splitList(myList, start, end):
temp = []
for i in range(start, end):
temp.append(myList[i])
return temp
def merge(myList, left, right):
leftSize = len(left)
rightSize = len(right)
# Three pointers for left, right, current list
leftP, rightP, primaryP = 0, 0, 0
while(leftP < leftSize and rightP < rightSize):
if(left[leftP] <= right[rightP]):
myList[primaryP] = left[leftP]
leftP += 1
else:
myList[primaryP] = right[rightP]
rightP += 1
primaryP += 1
# Add left over in left list
while(leftP < leftSize):
myList[primaryP] = left[leftP]
leftP += 1
primaryP += 1
# Add left over in right list
while(rightP < rightSize):
myList[primaryP] = right[rightP]
rightP += 1
primaryP += 1
def mergeSort(myList):
size = len(myList)
if(size <= 1):
return
# Get left size
leftSize = math.ceil(size/2)
# * in Other languages, You may need right list size
# ? rightSize = size - leftSize
left = splitList(myList, 0, leftSize)
right = splitList(myList, leftSize, size)
# Destructure into single array using Recursion
mergeSort(left)
mergeSort(right)
# merge
merge(myList, left, right)
# Testing Example
myList = [5, 2, 1, 4, 5, 2, 5, 7, 9, 8, 3]
print('Before Merge Sorting:')
print(*myList)
mergeSort(myList)
print('\nAfter Merge Sorting')
print(*myList)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment