# Algoritmos de JavaScript: combinación de ordenación

Merge sort es un algoritmo de clasificación que utiliza el concepto de "divide y vencerás".

Dada una matriz, primero la dividimos por la mitad y obtenemos 2 matrices.

Realizamos esta operación de forma recursiva, hasta llegar a matrices de 1 elemento.

Luego comenzamos a construir la matriz ordenada desde cero, ordenando los elementos individuales que obtuvimos.

Supongamos que nuestra matriz es esta:

``````[4, 3, 1, 2]We first divide the array into 2 arrays:
[4, 3]
[1, 2]then we recursively divide those arrays:
[4]
[3]and
[1]
[2]Then it’s time to construct the result, by ordering those pairs of elements first:
[3, 4]
[1, 2]Then we merge those 2 arrays:
[1, 2, 3, 4]Let’s do another example with more items in the array, this time using letters:
['e', 'g', 'a', 'd', 'f', 'c', 'b']We divide the array in 2:
['e', 'g', 'a']
['d', 'f', 'c', 'b']Then we divide the first array in 2:
['e']
['g', 'a']and we divide the second result:
['g']
['a']We now take the second part of the original array and we divide it in 2:
['d', 'f']
['c', 'b']We divide both items:
['d']
['f']['c']
['b']Now we have a list of 1-item arrays:
['e']
['g']
['a']
['d']
['f']
['c']
['b']Now we order them in pairs:
['e', 'g']
['a', 'd']
['d', 'f']
['c', 'b']Then we order the first 2 arrays and the last 2:
['a', 'd', 'e', 'g']
['c', 'b', 'd', 'f']Finally we merge the 2 arrays we got:
['a', 'b', 'c', 'd', 'e', 'f', 'g']We can implement this algorithm using 2 functions. The first called mergeSort, which is the function we’ll call, and another one called _mergeArrays, which takes care of merging the arrays. I prepended _ to its name, to signal it’s not meant to be called directly.
Here they are:
const _mergeArrays = (a, b) => {
const c = []
while (a.length && b.length) {
c.push(a[0] > b[0] ? b.shift() : a.shift())
}
//if we still have values, let’s add them at the end of c
while (a.length) {
c.push(a.shift())
}
while (b.length) {
c.push(b.shift())
}
return c
}
const mergeSort = (a) => {
if (a.length < 2) return a
const middle = Math.floor(a.length / 2)
const a_l = a.slice(0, middle)
const a_r = a.slice(middle, a.length)
const sorted_l = mergeSort(a_l)
const sorted_r = mergeSort(a_r)
return _mergeArrays(sorted_l, sorted_r)
}

Notice how in _mergeArrays() we initialize a resulting array c that we fill with the values of the 2 arrays a and b we pass to the function, ordered by value. Calling shift() on an array will remove the first item in the array, returning it, so we pass it to c.push() to add it to the c array.
The complexity of this algorithm is O(n log(n)), which makes it very efficient.

More js tutorials:

Things to avoid in JavaScript (the bad parts)

Deferreds and Promises in JavaScript (+ Ember.js example)

How to upload files to the server using JavaScript

JavaScript Coding Style

An introduction to JavaScript Arrays

Introduction to the JavaScript Programming Language

The Complete ECMAScript 2015-2019 Guide

Understanding JavaScript Promises

The Lexical Structure of JavaScript

JavaScript Types

JavaScript Variables

A list of sample Web App Ideas

An introduction to Functional Programming with JavaScript

Modern Asynchronous JavaScript with Async and Await

JavaScript Loops and Scope

The Map JavaScript Data Structure

The Set JavaScript Data Structure

A guide to JavaScript Template Literals

JavaScript Expressions

Discover JavaScript Timers

JavaScript Events Explained

JavaScript Loops

Write JavaScript loops using map, filter, reduce and find

The JavaScript Event Loop

JavaScript Functions

The JavaScript Glossary

JavaScript Closures explained

A tutorial to JavaScript Arrow Functions

A guide to JavaScript Regular Expressions

How to check if a string contains a substring in JavaScript

How to remove an item from an Array in JavaScript

How to deep clone a JavaScript object

Introduction to Unicode and UTF-8

Unicode in JavaScript

How to uppercase the first letter of a string in JavaScript

How to format a number as a currency value in JavaScript

How to convert a string to a number in JavaScript

this in JavaScript

How to get the current timestamp in JavaScript

JavaScript Strict Mode

JavaScript Immediately-invoked Function Expressions (IIFE)

How to redirect to another web page using JavaScript

How to remove a property from a JavaScript object

How to append an item to an array in JavaScript

How to check if a JavaScript object property is undefined

Introduction to ES Modules

Introduction to CommonJS

JavaScript Asynchronous Programming and Callbacks

How to replace all occurrences of a string in JavaScript

A quick reference guide to Modern JavaScript Syntax

How to trim the leading zero in a number in JavaScript

How to inspect a JavaScript object

The definitive guide to JavaScript Dates

A Moment.js tutorial

Semicolons in JavaScript

The JavaScript Arithmetic operators

The JavaScript Math object

Generate random and unique strings in JavaScript

How to make your JavaScript functions sleep

JavaScript Prototypal Inheritance

JavaScript Exceptions

How to use JavaScript Classes

The JavaScript Cookbook

Quotes in JavaScript

How to validate an email address in JavaScript

How to get the unique properties of a set of objects in a JavaScript array

How to check if a string starts with another in JavaScript

How to create a multiline string in JavaScript

The ES6 Guide

How to get the current URL in JavaScript

The ES2016 Guide

How to initialize a new array with values in JavaScript

The ES2017 Guide

The ES2018 Guide

How to use Async and Await with Array.prototype.map()

Async vs sync code

How to generate a random number between two numbers in JavaScript

HTML Canvas API Tutorial

How to get the index of an iteration in a for-of loop in JavaScript

What is a Single Page Application?

An introduction to WebAssembly

Introduction to JSON

The JSONP Guide

Should you use or learn jQuery in 2020?

How to hide a DOM element using plain JavaScript

How to merge two objects in JavaScript

How to empty a JavaScript array

How to encode a URL with JavaScript

How to set default parameter values in JavaScript

How to sort an array of objects by a property value in JavaScript

How to count the number of properties in a JavaScript object

call() and apply() in JavaScript

Introduction to PeerJS, the WebRTC library

Work with objects and arrays using Rest and Spread

Destructuring Objects and Arrays in JavaScript

The definitive guide to debugging JavaScript

The TypeScript Guide

Dynamically select a method of an object in JavaScript

Passing undefined to JavaScript Immediately-invoked Function Expressions

Loosely typed vs strongly typed languages

How to style DOM elements using JavaScript

Casting in JavaScript

JavaScript Generators Tutorial

The node_modules folder size is not a problem. It's a privilege

How to solve the unexpected identifier error when importing modules in JavaScript

How to list all methods of an object in JavaScript

The String replace() method

The String search() method

How I run little JavaScript snippets

The ES2019 Guide

The String charAt() method

The String charCodeAt() method

The String codePointAt() method

The String concat() method

The String endsWith() method

The String includes() method

The String indexOf() method

The String lastIndexOf() method

The String localeCompare() method

The String match() method

The String normalize() method

The String repeat() method

The String slice() method

The String split() method

The String startsWith() method

The String substring() method

The String toLocaleLowerCase() method

The String toLocaleUpperCase() method

The String toLowerCase() method

The String toString() method

The String toUpperCase() method

The String trim() method

The String trimEnd() method

The String trimStart() method

Memoization in JavaScript

The String valueOf() method

JavaScript Reference: String

The Number isInteger() method

The Number isNaN() method

The Number isSafeInteger() method

The Number parseFloat() method

The Number parseInt() method

The Number toString() method

The Number valueOf() method

The Number toPrecision() method

The Number toExponential() method

The Number toLocaleString() method

The Number toFixed() method

The Number isFinite() method

JavaScript Reference: Number

JavaScript Property Descriptors

The Object assign() method

The Object create() method

The Object defineProperties() method

The Object defineProperty() method

The Object entries() method

The Object freeze() method

The Object getOwnPropertyDescriptor() method

The Object getOwnPropertyDescriptors() method

The Object getOwnPropertyNames() method

The Object getOwnPropertySymbols() method

The Object getPrototypeOf() method

The Object is() method

The Object isExtensible() method

The Object isFrozen() method

The Object isSealed() method

The Object keys() method

The Object preventExtensions() method

The Object seal() method

The Object setPrototypeOf() method

The Object values() method

The Object hasOwnProperty() method

The Object isPrototypeOf() method

The Object propertyIsEnumerable() method

The Object toLocaleString() method

The Object toString() method

The Object valueOf() method

JavaScript Reference: Object

JavaScript Assignment Operator

JavaScript Internationalization

JavaScript typeof Operator

JavaScript new Operator

JavaScript Comparison Operators

JavaScript Operators Precedence Rules

JavaScript instanceof Operator

JavaScript Statements

JavaScript Scope

JavaScript Type Conversions (casting)

JavaScript Equality Operators

The JavaScript if/else conditional

The JavaScript Switch Conditional

The JavaScript delete Operator

JavaScript Function Parameters

JavaScript Return Values

JavaScript Logical Operators

JavaScript Ternary Operator

JavaScript Recursion

JavaScript Object Properties

JavaScript Error Objects

The JavaScript Global Object

The JavaScript filter() Function

The JavaScript map() Function

The JavaScript reduce() Function

The JavaScript `in` operator

JavaScript Operators

How to get the value of a CSS property in JavaScript

How to add an event listener to multiple elements in JavaScript

JavaScript Private Class Fields

How to sort an array by date value in JavaScript

JavaScript Public Class Fields

JavaScript Symbols

How to use the JavaScript bcrypt library

How to rename fields when using object destructuring

How to check types in JavaScript without using TypeScript

How to check if a JavaScript array contains a specific value

What does the double negation operator !! do in JavaScript?

Which equal operator should be used in JavaScript comparisons? == vs ===

Is JavaScript still worth learning?

How to return the result of an asynchronous function in JavaScript

How to check if an object is empty in JavaScript

How to break out of a for loop in JavaScript

How to add item to an array at a specific index in JavaScript

Why you should not modify a JavaScript object prototype

What's the difference between using let and var in JavaScript?

Links used to activate JavaScript functions

How to join two strings in JavaScript

How to join two arrays in JavaScript

How to check if a JavaScript value is an array?

How to get last element of an array in JavaScript?

How to send urlencoded data using Axios

How to get tomorrow's date using JavaScript

How to get yesterday's date using JavaScript

How to get the month name from a JavaScript date

How to check if two dates are the same day in JavaScript

How to check if a date refers to a day in the past in JavaScript

JavaScript labeled statements

How to wait for 2 or more promises to resolve in JavaScript

How to get the days between 2 dates in JavaScript

How to upload a file using Fetch

How to format a date in JavaScript

How to iterate over object properties in JavaScript

How to calculate the number of days between 2 dates in JavaScript

How to use top-level await in ES Modules

JavaScript Dynamic Imports

JavaScript Optional Chaining

How to replace white space inside a string in JavaScript

JavaScript Nullish Coalescing

How to flatten an array in JavaScript

How to send the authorization header using Axios

List of keywords and reserved words in JavaScript

How to convert an Array to a String in JavaScript

How to remove all the node_modules folders content

How to remove duplicates from a JavaScript array

Let vs Const in JavaScript

The same POST API call in various JavaScript libraries

How to get the first n items in an array in JS

How to divide an array in multiple equal parts in JS

How to slow down a loop in JavaScript

How to load an image in an HTML canvas

How to cut a string into words in JavaScript

How to divide an array in half in JavaScript

How to write text into to an HTML canvas

How to remove the last character of a string in JavaScript

How to remove the first character of a string in JavaScript

How to fix the TypeError: Cannot assign to read only property 'exports' of object '#&lt;Object&gt;' error

How to create an exit intent popup

How to check if an element is a descendant of another

How to force credentials to every Axios request

How to solve the "is not a function" error in JavaScript

Gatsby, how to change the favicon

How to detect dark mode using JavaScript

Parcel, how to fix the `regeneratorRuntime is not defined` error

How to detect if an Adblocker is being used with JavaScript

Object destructuring with types in TypeScript

The Deno Handbook: a concise introduction to Deno 🦕

How to get the last segment of a path or URL using JavaScript

How to shuffle elements in a JavaScript array

How to check if a key exists in a JavaScript object

Event bubbling and event capturing

event.stopPropagation vs event.preventDefault() vs. return false in DOM events

Primitive types vs objects in JavaScript

How can you tell what type a value is, in JavaScript?

How to return multiple values from a function in JavaScript

Arrow functions vs regular functions in JavaScript

In which ways can we access the value of a property of an object?

What is the difference between null and undefined in JavaScript?

What's the difference between a method and a function?

What are the ways we can break out of a loop in JavaScript?

The JavaScript for..of loop

What is object destructuring in JavaScript?

What is hoisting in JavaScript?

How to change commas into dots with JavaScript

The importance of timing when working with the DOM

How to reverse a JavaScript array

How to check if a value is a number in JavaScript

How to accept unlimited parameters in a JavaScript function

JavaScript Proxy Objects

Event delegation in the browser using vanilla JavaScript

The JavaScript super keyword

Introduction to XState

Are values passed by reference or by value in JavaScript?

Custom events in JavaScript

Custom errors in JavaScript

Namespaces in JavaScript

A curious usage of commas in JavaScript

Chaining method calls in JavaScript

How to handle promise rejections

How to swap two array elements in JavaScript

How I fixed a "cb.apply is not a function" error while using Gitbook

How to add an item at the beginning of an array in JavaScript

Gatsby, fix the "cannot find module gatsby-cli/lib/reporter" error

How to get the index of an item in a JavaScript array

How to test for an empty object in JavaScript

How to destructure an object to existing variables in JavaScript

The Array JavaScript Data Structure

The Stack JavaScript Data Structure

JavaScript Data Structures: Queue

JavaScript Data Structures: Set

JavaScript Data Structures: Dictionaries

JavaScript, how to export a function

JavaScript, how to export multiple functions

JavaScript, how to exit a function

JavaScript, how to find a character in a string

JavaScript, how to filter an array

JavaScript, how to extend a class

JavaScript, how to find duplicates in an array

JavaScript, how to replace an item of an array

JavaScript Algorithms: Linear Search

JavaScript Algorithms: Binary Search

JavaScript Algorithms: Selection Sort

JavaScript Algorithms: Quicksort

JavaScript Algorithms: Merge Sort

JavaScript Algorithms: Bubble Sort

``````