In this post I will show how to do a simple implementation of the Merge Sort in React.
Initially I wanted to use this as an excuse to learn React. However, I think this ended up being a review of CS material from a distant past, rather than an advanced React tutorial.
Anyway, here is a quick recap of the merge sort:
Merge Sort
Merge Sort is an example of an optimized sorting algorithm.
Efficient algorithms in Computer Science are often based around some form of “divide and conquer”.
The general idea is to break the original problem space into smaller and smaller pieces, often cutting it in half for every iteration.
This is exactly how the merge sort works as well. We start with with a single array of numbers that we recursively cut in half until we are left with a series of single item arrays.
An array of size one is the base case for the recursion. It is also by definition a sorted list. Once the original array is broken down into single item arrays, the next phase is to reconstruct a single array from the smaller fragments.
This is usually referred to as the “merge” phase of the algorithm. Basically we work our way back up the call chain by merging and sorting all the smaller arrays into a single sorted array.
The UI of my demo application tries to visualize this divide and merge process. See the screenshot below:
Follow the diagram top to bottom.
Source Code
I have put all the code on
Github, but let’s take a look at the merge sort implementation below:
import { Partition } from './partition';
export class SortingService {
partitions = [];
mergeSort(currentPartition) {
if (currentPartition.isSingleItemList()) {
return currentPartition;
}
let left = currentPartition.getLeftHalf();
let right = currentPartition.getRightHalf();
this.buildModel(left, {left: [...currentPartition.items]});
this.buildModel(right, {left: [...currentPartition.items]});
return this.merge(this.mergeSort(left), this.mergeSort(right));
}
merge(left, right){
let result = [];
let parts = {left: [...left.items], right: [...right.items]};
while (!left.isEmpty() && !right.isEmpty()) {
if (left.first() < right.first()){
result.push(left.items.shift());
}
else {
result.push(right.items.shift());
}
}
result = result.concat(left.items).concat(right.items);
let newPartition = new Partition(`${left.id}-${right.id}`, result);
this.buildModel(newPartition, parts);
return newPartition;
}
buildModel(res, part) {
let nodeIndex = this.partitions.findIndex(p => p.parentId === res.parentId);
if(nodeIndex >= 0) {
this.partitions[nodeIndex].fragments.push(res.items.slice());
this.partitions[nodeIndex].part1 = [];
this.partitions[nodeIndex].part2 = part.left;
this.partitions[nodeIndex].descr = '*split from ';
this.partitions[nodeIndex].show = 'hide';
}
else {
let node = {parentId: res.parentId, fragments: []};
node.part1 = part.left;
node.descr = '*merged from ';
node.part2 = part.right;
node.show = 'group';
node.fragments.push(res.items.slice());
this.partitions.push(node);
}
}
}
I have also included the React component part here:
import React, { Component } from 'react';
import { SortingService } from './sorting-service';
import { Partition } from './partition';
export class SortingComponent extends Component {
unsorted = [55, 1, 2, 4, 9, 77, 3, 65, -1, 999];
constructor() {
super();
this.state = {partitions: []};
this.sortingService = new SortingService();
}
componentDidMount() {
let partition = new Partition(0, this.unsorted);
this.sortingService.mergeSort(partition);
this.setState({partitions: this.sortingService.partitions});
}
render() {
let fragments = this.state.partitions.map((node, i1) => {
return <div key={i1} className="fragment-row" >
{
node.fragments.map((numbers, i2) =>
<span>
<span className="group" key={i2}>
{
numbers.map((number, index) => {
return <span key={index} className="number">{number}</span>
})
}
</span>
</span>
)
}
<span>{node.descr}</span>
<span className={node.show}>
{(node.part1 || []).map((n, index) => {
return <span key={index} className="number">{n}</span>
})}
</span>
<span className="group">
{(node.part2 || []).map((n, index) => {
return <span key={index} className="number">{n}</span>
})}
</span>
</div>
});
return (
<div>
<h4>Merge Sort</h4>
<div className="fragment-row">
<strong>Sample Numbers: { this.unsorted.join(' ') }</strong>
</div>
{fragments}
</div>
);
}
}
Finally I am including a model class that I am using to represent the array fragments that are generated as the algorithm walk the original array.
export class Partition {
static nextId = 0;
constructor(parentId, items) {
this.items = items;
this.parentId = `parentId${parentId}`;
this.id = (Partition.nextId++).toString();
this.middle = this.findMiddle();
}
isEmpty() {
return this.items.length === 0;
}
isSingleItemList() {
return this.items.length < 2;
}
findMiddle() {
return Math.floor(this.items.length / 2);
}
first() {
return this.items[0];
}
getLeftHalf() {
let items = this.items.slice(0, this.middle);
return new Partition(this.id, items);
}
getRightHalf() {
let items = this.items.slice(this.middle, this.items.length);
return new Partition(this.id, items);
}
}