<h3 id="introduction">Introduction</h3>
If you're majoring in Computer Science, Insertion Sort is most likely one of the first sorting algorithms you have heard of. It is intuitive and easy to <a href="#implementation">implement</a>, but it's very slow on large arrays and is rarely used to sort them.
Insertion Sort is very simple and intuitive to implement, which is one of the reasons it's generally taught at an early stage in programming. It's a stable, in-place algorithm, that works really well for nearly-sorted or small arrays.
Let's elaborate these terms:
<ul>
<li>In-place: Requires a small, constant additional space (no matter the input size of the collection), but rewrites the original memory locations of the elements in the collection.</li>
<li>Stable: The algorithm maintains the relative order of equal objects from the initial array. In other words, say your company's employee database returns &quot;Dave Watson&quot; and &quot;Dave Brown&quot; as two employees, in that specific order. If you were to sort them by their (shared) first name, a stable algorithm would guarantee that this order remains unchanged.</li>
</ul>

 <div class="alert alert-note">
 <div class="flex">
 
 <div class="flex-shrink-0 mr-3">
 <img src="/assets/images/icon-information-circle-solid.svg" class="icon" aria-hidden="true" />
 </div>
 
 <div class="w-full">
 Note: Insertion Sort doesn't need to know the entire array in advance before sorting. The algorithm can receive one element at a time. This is great if we want to add more elements to be sorted - the algorithm only inserts that element in its proper place without &quot;re-doing&quot; the whole sort.

 </div>
 </div>
 </div>
 Insertion Sort is used rather often in practice, because of how efficient it is for small (~10 items) data sets. We will talk more about that <a href="#insertionsortinpractice">later</a>.
<h3 id="theideabehindtheinsertionsort">The Idea Behind the Insertion Sort</h3>
Insertion sort is often illustrated by comparing it to sorting a hand of cards while playing rummy. For those of you unfamiliar with the game, most players want the cards in their hand sorted in ascending order so they can quickly see which combinations they have at their disposal.
The dealer deals out 14 cards to you, you pick them up one by one and put them in your hand in the right order. During this entire process, your hand holds the sorted &quot;subarray&quot; of your cards, while the remaining face-down cards on the table are unsorted - from which you take cards one by one, and put them in your hand.
<blockquote>
In that manner, the Insertion sort partitions an array into a &quot;sorted&quot; subarray and an &quot;unsorted&quot; subarray. In the beginning, the sorted subarray contains only the first element of our original array.
</blockquote>
The first element in the unsorted array is evaluated so that we can insert it into its proper place in the sorted subarray. The insertion is done by moving all elements larger than the new element one position to the right. Continue doing this until our entire array is sorted, as simple as that.

 <div class="alert alert-note">
 <div class="flex">
 
 <div class="flex-shrink-0 mr-3">
 <img src="/assets/images/icon-information-circle-solid.svg" class="icon" aria-hidden="true" />
 </div>
 
 <div class="w-full">
 Note: Keep in mind that when we say an element is larger or smaller than another element - it doesn't necessarily mean larger or smaller integers.
We can define the words &quot;larger&quot; and &quot;smaller&quot; however we like when using custom objects. For example, point A can be &quot;larger&quot; than point B if it's further away from the center of the coordinate system.

 </div>
 </div>
 </div>
 We will mark the sorted subarray with bolded numbers, and use the following array to illustrate the algorithm:
<ul>
<li>8, 5, 4, 10, 9</li>
</ul>
The first step would be to &quot;add&quot; 8 to our sorted subarray.
<ul>
<li>8, 5, 4, 10, 9</li>
</ul>
Now we take a look at the first unsorted element - 5. We keep that value in a separate variable, for example <code>current</code>, for safe-keeping. 5 is less than 8. We move 8 one place to the right, effectively overwriting the 5 that was previously stored there (hence the separate variable for safekeeping):
<ul>
<li>8, 8, 4, 10, 9 (<code>current</code> = 5)</li>
</ul>
5 is lesser than all the elements in our sorted subarray, so we insert it into the first position:
<ul>
<li>5, 8, 4, 10, 9</li>
</ul>
Next, we look at number 4. We save that value in the <code>current</code>. 4 is less than 8 so we move 8 to the right, and do the same with 5.
<ul>
<li>5, 5, 8, 10, 9 (<code>current</code> = 4)</li>
</ul>
Again we've encountered an element lesser than our entire sorted subarray, so we put it in the first position:
<ul>
<li>4, 5, 8, 10, 9</li>
</ul>
10 is greater than our rightmost element in the sorted subarray and is therefore larger than any of the elements to the left of 8. So we simply move on to the next element:
<ul>
<li>4, 5, 8, 10, 9</li>
</ul>
9 is less than 10, so we move 10 to the right:
<ul>
<li>4, 5, 8, 10, 10 (<code>current</code> = 9)</li>
</ul>
However, 9 is greater than 8, so we simply insert 9 right after 8.
<ul>
<li>4, 5, 8, 9, 10</li>
</ul>
<h3 id="howtoimplementbubblesortinpython">How to Implement Bubble Sort in Python</h3>
As we have previously mentioned, Insertion Sort is fairly easy to implement. We'll implement it first on a simple array of integers and then on some custom objects.
In practice, it's much more likely that you'll be working with objects and sorting them based on certain criteria.
<h4 id="sortingarrays">Sorting Arrays</h4>
<pre><code class="hljs">def insertion_sort(array):

 # We start from 1 since the first element is trivially sorted
 for index in range(1, len(array)):
 currentValue = array[index]
 currentPosition = index

 # As long as we haven&#x27;t reached the beginning and there is an element
 # in our sorted array larger than the one we&#x27;re trying to insert - move
 # that element to the right
 while currentPosition &gt; 0 and array[currentPosition - 1] &gt; currentValue:
 array[currentPosition] = array[currentPosition -1]
 currentPosition = currentPosition - 1


 # We have either reached the beginning of the array or we have found
 # an element of the sorted array that is smaller than the element
 # we&#x27;re trying to insert at index currentPosition - 1.
 # Either way - we insert the element at currentPosition
 array[currentPosition] = currentValue
</code></pre>
Let's populate a simple array and sort it:
<pre><code class="hljs">array = [4, 22, 41, 40, 27, 30, 36, 16, 42, 37, 14, 39, 3, 6, 34, 9, 21, 2, 29, 47]
insertion_sort(array)
print(&quot;sorted array: &quot; + str(array))
</code></pre>
Output:
<pre><code class="hljs">sorted array: [2, 3, 4, 6, 9, 14, 16, 21, 22, 27, 29, 30, 34, 36, 37, 39, 40, 41, 42, 47]
</code></pre>

 <div class="alert alert-note">
 <div class="flex">
 
 <div class="flex-shrink-0 mr-3">
 <img src="/assets/images/icon-information-circle-solid.svg" class="icon" aria-hidden="true" />
 </div>
 
 <div class="w-full">
 Note: It would have been technically incorrect if we reversed the order of conditions in our <code>while</code> loop. That is, if we first checked whether <code>array[currentPosition-1] &gt; currentValue</code> before checking whether <code>currentPosition &gt; 0</code>.

 </div>
 </div>
 </div>
 This would mean that if we did indeed reach the 0th element, we would first check whether <code>array[-1] &gt; currentValue</code>. In Python, this is &quot;fine&quot;, although technically incorrect, since it wouldn't cause the loop to end prematurely or continue when it shouldn't.
This is because if we had reached the zeroth element, the second condition of <code>currentPosition &gt; 0</code> would fail regardless of the first condition, and cause the loop to break. In Python <code>array[-1] &gt; currentValue</code> is equivalent to <code>array[len(array) - 2] &gt; currentValue</code> and the interpreter wouldn't complain, but this is not a comparison we actually want to happen.
This reversed order of conditions is a bad idea. In a lot of cases, it can lead to unexpected results that can be hard to debug because there is no syntactic or semantic error. Most programming languages would &quot;complain&quot; for trying to access the <code>-1</code>st element, but Python won't complain and it's easy to miss such a mistake.
<blockquote>
The takeaway advice from this is to always check whether the index is valid before using it to access elements.
</blockquote>
<h4 id="sortingcustomobjects">Sorting Custom Objects</h4>
We've mentioned before that we can define &quot;greater than&quot; and &quot;lesser than&quot; however we want - that the definition doesn't need to rely solely on integers. There are several ways we can change our algorithm to work with custom objects.
We could redefine the actual comparison operators for our custom class and keep the same algorithm code as above. However, that would mean that we'd need to <a target="_blank" href="/overloading-functions-and-operators-in-python">overload those operators</a> if we wanted to sort the objects of our class in a different way.
Arguably the best way to use Insertion Sort for custom classes is to pass another argument to the <code>insertion_sort()</code> method - specifically a comparison method. The most convenient way to do this is by using a custom <a target="_blank" href="/lambda-functions-in-python/">lambda function</a> when calling the sorting method.
In this implementation, we'll sort points where a &quot;smaller&quot; point is the one with a lower <code>x</code> coordinate.
First, we'll define our <code>Point</code> class:
<pre><code class="hljs">class Point:
 def __init__(self, x, y):
 self.x = x
 self.y = y

 def __str__(self):
 return str.format(&quot;({},{})&quot;, self.x, self.y)
</code></pre>
Then we make a slight change to our <code>insertion_sort</code> method to accommodate custom sorting:
<pre><code class="hljs">def insertion_sort(array, compare_function):
 for index in range(1, len(array)):
 currentValue = array[index]
 currentPosition = index

 while currentPosition &gt; 0 and compare_function(array[currentPosition - 1], currentValue):
 array[currentPosition] = array[currentPosition - 1]
 currentPosition = currentPosition - 1

 array[currentPosition] = currentValue
</code></pre>
Finally, we test the program:
<pre><code class="hljs">A = Point(1,2)
B = Point(4,4)
C = Point(3,1)
D = Point(10,0)

array = [A,B,C,D]

# We sort by the x coordinate, ascending
insertion_sort(array, lambda a, b: a.x &gt; b.x)

for point in array:
 print(point)
</code></pre>
We get the output:
<pre><code class="hljs">(1,2)
(3,1)
(4,4)
(10,0)
</code></pre>
This algorithm will now work for any type of array, as long as we provide an appropriate comparison function.
<h3 id="insertionsortinpractice">Insertion Sort in Practice</h3>
Insertion sort may seem like a slow algorithm, and indeed in most cases, it is too slow for any practical use with its O(n2) time complexity. However, as we've mentioned, it's very efficient on small arrays and on nearly sorted arrays.
This makes Insertion Sort very relevant for use in combination with algorithms that work well on large data sets.
For example, Java used a Dual Pivot <a target="_blank" href="/quicksort-in-python">Quick Sort</a> as the primary sorting algorithm but used Insertion Sort whenever the array (or subarray created by Quick Sort) had less than 7 elements.
Another efficient combination is simply ignoring all small subarrays created by Quick Sort, and then passing the final, nearly-sorted array, through Insertion Sort.
Another place where Insertion Sort left its mark is with a very popular algorithm called Shell Sort. Shell Sort works by calling Insertion Sort to sort pairs of elements far apart from each other, then incrementally reducing the gap between elements to be compared.
Essentially it makes a lot of Insertion Sort calls to first small, and then nearly-sorted larger arrays, harnessing all the advantages it can.
<h3 id="conclusion">Conclusion</h3>
Insertion Sort is a very simple, generally inefficient algorithm that nonetheless has several specific advantages that make it relevant even after many other, generally more efficient algorithms have been developed.
It remains a great algorithm for introducing future software developers into the world of sorting algorithms and is still used in practice for specific scenarios in which it shines.

Olivera Popović

Dimitrije Stamenic

Insertion Sort is a simple sorting algorithm that works wonders on small collections. It often used alongside Quicksort and Merge Sort in the final stages. In this article, we'll implement Insertion Sort in Python.

Insertion Sort in Python

Git is a great tool for tracking all of the files in a project, whether you have only a few to track or thousands. But just because a file exists in your project doesn't mean you automatically want to keep track of it and its changes over the lifetime of the project.
In this article we'll see a bit of background on why it's important to tell Git to ignore certain files, how to actually do it, and some best practices.
<h2 id="whyusegitignore">Why use .gitignore?</h2>
Manually ignoring files that you don't want to track is manageable on a small-scale project, but as soon as your project starts to grow and include tens or hundreds of non-version controlled files, it can then become a big problem. These files will start to clutter the &quot;Untracked files&quot; list, which may cause you to overlook legitimate files that need to be in the repo.
To help with this problem, Git has an &quot;ignore&quot; mechanism in the form of a file called <code>.gitignore</code>. With this file and very simple pattern matching, you can tell Git which types of files you want it to ignore and not track in your repo. If a filename in your project matches one of the patterns in the <code>.gitignore</code> file then Git won't attempt to track the file and it won't show up in the &quot;Untracked files&quot; list.
<h2 id="whatfilestoignore">What Files to Ignore</h2>
A lot of this comes down to personal preference, but in general I tend to follow these general rules on which files to not track:
<ul>
<li>System files (i.e. Mac's <code>.DS_Store</code>)</li>
<li>App configuration files (i.e. <code>app.config</code>, <code>.env</code>, etc.)</li>
<li>Build artifacts (i.e. <code>*.pyc</code>)</li>
<li>Installed dependencies (i.e. <code>node_modules</code>)</li>
<li>Non-documenation and personal text files (i.e. <code>todo.txt</code>)</li>
<li>Application data and logs (i.e. <code>*.log</code>, <code>*.sqlite</code>, etc.)</li>
</ul>
There are quite a few other files types that are often ignored, but a lot of this comes down to personal preference, like the following:
<ul>
<li>Dev configuration files (i.e. <code>.jshintrc</code>)</li>
<li>Generated or minified source code (i.e. <code>*.min.js</code>)</li>
<li><code>.gitignore</code></li>
</ul>
Yes, even tracking of the <code>.gitignore</code> file itself is debated.
The advice given here may change depending on who you talk to, so you may want to take some of this with a grain of salt. Everyone has their opinions on what should or shouldn't be tracked, so your best option is to review both sides of the debate and then make a decision for yourself based on what's best for your project.
<h2 id="usinggitignore">Using .gitignore</h2>
The basics of using this ignore feature are pretty straight forward, which is what we'll go over in this section.
For the sake of our example, let's say we have a new project with the following untracked files:
<pre><code class="hljs">$ git status
On branch master

Initial commit

Untracked files:
 (use &quot;git add &lt;file&gt;...&quot; to include in what will be committed)

 .DS_Store
 .env-dev
 .env-prod
 index.js
 node_modules/
 package-lock.json
 package.json
</code></pre>
It's a bit pointless to track the <code>.DS_Store</code> and <code>node_modules/</code> files in our repo, so we'll want to ignore these. To do so, we'll first create a file in the project's root directory named <code>.gitignore</code>:
<pre><code class="hljs">$ touch .gitignore
</code></pre>
The simplest way to ignore a file, and most common, is to simply add the full filename to the ignore file. So to ignore the above files, for example, we'll want to add the following:
<pre><code class="hljs">.DS_Store
node_modules
</code></pre>
Once saved, Git will now show us the following untracked files:
<pre><code class="hljs">$ git status

...

Untracked files:
 (use &quot;git add &lt;file&gt;...&quot; to include in what will be committed)

 .env-dev
 .env-prod
 .gitignore
 index.js
 package-lock.json
 package.json
</code></pre>
Both <code>.DS_Store</code> and <code>node_modules</code> are now gone from the &quot;Untracked files&quot; list, but we still have a few that we want to get rid of, <code>.env-dev</code> and <code>.env-prod</code>. To avoid having to explicitly add each to <code>.gitignore</code> (especially if we have to add more of these files for test and staging environments), we'll use a wildcard:
<pre><code class="hljs">.DS_Store
node_modules
.env-*
</code></pre>
And now our &quot;Untracked files&quot; list has been reduced even further:
<pre><code class="hljs">$ git status

...

Untracked files:
 (use &quot;git add &lt;file&gt;...&quot; to include in what will be committed)

 .gitignore
 index.js
 package-lock.json
 package.json
</code></pre>
The wildcard character (<code>*</code>) will match anything except for a slash. And using two wildcard characters in a row (<code>**</code>) followed by a slash will match your pattern in all directories. So, for example, <code>public/**/*.min.js</code> will ignore all minified JavaScript files in the <code>public</code> directory, regardless of how many directories deep they are.
The Git ignore mechanism also supports some simple <a rel="nofollow noopener" target="_blank" href="https://en.wikipedia.org/wiki/Regular_expression">regular expression</a>-like syntax, with some extra syntax of its own:
<ul>
<li><code>[a-zA-Z]</code>: Match a range of characters</li>
<li><code>?</code>: Match 0 or 1 occurrences of the preceding element</li>
<li><code>!</code>: Negates the match or preceding character</li>
</ul>
Git also allows you to add comments to this file, which start with a <code>#</code>. This is very useful for organizing the file or adding explanations about why certain patterns were added.
<h2 id="hierarchyofgitignorefiles">Hierarchy of .gitignore Files</h2>
Git actually checks more than just the local <code>.gitignore</code> file for which files it should ignore. As we've seen so far, the most common location is to place a <code>.gitignore</code> file in the root directory of your project. Another option is to have a <code>.gitignore</code> file nested in a directory in your project. While less common in practice, this can be useful for applying an entire ignore file on a subdirectory that has many rules of its own.
Another useful feature is a global ignore file. This is typically a <code>.gitignore</code> file placed in your home directory:
<pre><code class="hljs">$ touch ~/.gitignore
</code></pre>
If needed, you can change the location of this global file using the following command:
<pre><code class="hljs">$ git config --global core.excludesFile ~/.gitignore
</code></pre>
Any patterns placed in this file should be for file types that you are positive you'll never want to track, like the <code>.DS_Store</code> file for you Mac users. It's easy to forget about this global ignore file, which can cause a lot of confusion or problems when you miss committing a file because it was ignored globally.
<h2 id="committingignoredfiles">Committing Ignored Files</h2>
Let's say you have an exception you want to make for a file that's usually ignored, but for whatever reason this project in particular needs it. In cases like this you have a few options:
<ol>
<li>Tell Git to not ignore this file by prefixing the file name with a <code>!</code> in .gitignore, i.e. <code>!.env</code>. This will override any global ignore files or ignore files in parent directories.</li>
<li>Use the <code>--force</code> option (or <code>-f</code> flag) when staging your files, i.e. <code>git add .env --force</code></li>
</ol>
<h2 id="conclusion">Conclusion</h2>
In this article we saw how Git provides a mechanism for us to tell it which files should not be tracked in our repo, preventing us from having to manually prevent files from being added. This is a powerful feature that provides a rich syntax, as well as a hierarchy to better control which files are ignored and which aren't.

Scott Robinson

Manually ignoring files is manageable on a small project. This task gets out of hand as soon as your project gets big, which can cause many manual errors and issues with your build. In this article, we'll see how to use .gitignore to ignore files we want to be omitted from the repo.

Git: Ignore Files with .gitignore

Dan Nelson

Dimensionality reduction selects the most important components of the feature space, preserving them, to combat overfitting. In this article, we'll reduce the dimensions of several datasets using a wide variety of techniques in Python using Scikit-Learn.

Dimensionality Reduction in Python with Scikit-Learn

<h2 id="introduction">Introduction</h2>
Sorting is a crucial aspect of digesting data. For us humans, it's much more natural to sort things that have something in common like the date of publishing, alphabetical order, articles belonging to an author, from smallest to largest, etc. This makes it a lot easier to comprehend the data as it's logically connected rather than dispersed all around.
And just as important, sorted arrays are easier for computers to work with. For example, a sorted array can be searched much faster, like with the <a rel="nofollow noopener" target="_blank" href="https://en.wikipedia.org/wiki/Binary_search_algorithm">binary search</a> algorithm, which runs in O(logn) time. An algorithm like this just doesn't work without a sorted array.
<h2 id="mergesort">Merge Sort</h2>
Merge sort is a divide-and-conquer algorithm, which recursively calls itself on halved portions of the initial collection.
That being said, it sounds a lot like <a rel="nofollow noopener" target="_blank" href="https://en.wikipedia.org/wiki/Quicksort">Quicksort</a>, which also partitions the collection and then recursively calls itself on the partitioned collections (which are typically halves).
The main difference is the fact that Quicksort is an internal, in-place sorting algorithm while Merge Sort is an external, out-of-place sorting algorithm.
This is typically done with collections which are too large to load into memory, and we load them chunk by chunk as they're needed. So Merge Sort doesn't need to store the whole collection into the memory from which it can easily and randomly access each and every element at any given time. Rather, the collection can be stored at an external place, such as a disk (or much longer ago - tape), from which required elements are loaded.
That being said, Merge Sort has to deal with making such loading and unloading optimal as it can get quite slow with big collections.
As mentioned above, Merge Sort is an &quot;out-of-place&quot; sorting algorithm. What this means is that Merge Sort does not sort and store the elements in the memory addresses of the collection given to it, but instead it creates and returns a completely new collection that is the sorted version of the one provided to it.
This is an important distinction because of memory usage. For very large arrays this would be a disadvantage because the data will be duplicated, which can memory problems on some systems.
Here's a visual representation of how it works:
<img src="https://s3.amazonaws.com/stackabuse/media/sorting-algorithms-in-java-1.png" alt="merge sort visual representation">
<h2 id="implementation">Implementation</h2>
To fascilitate the algorithm, we'll be using two methods - <code>mergeSort()</code> which will partition the collection and recursivelly call itself, and its helper method, <code>merge()</code> which will merge the results in the correct order.
Let's start off with <code>mergeSort()</code>:
<pre><code class="hljs">public static void mergeSort(int[] array, int low, int high) {
 if (high &lt;= low) return;

 int mid = (low+high)/2;
 mergeSort(array, low, mid);
 mergeSort(array, mid+1, high);
 merge(array, low, mid, high);
}
</code></pre>
This part is pretty straightforward - we provide an array to be sorted and it's <code>low</code> and <code>high</code> pointers. If the <code>high</code> pointer ends up being lower or equal to the <code>low</code> pointer, we simply <code>return</code>.
Otherwise, we partition the array into two halves and call <code>mergeSort</code> from the start of the array to the middle, and then call it from the middle to the end.
Ultimately, we call the <code>merge()</code> method, which merges the results into a sorted array:
<pre><code class="hljs">public static void merge(int[] array, int low, int mid, int high) {
 // Creating temporary subarrays
 int leftArray[] = new int[mid - low + 1];
 int rightArray[] = new int[high - mid];

 // Copying our subarrays into temporaries
 for (int i = 0; i &lt; leftArray.length; i++)
 leftArray[i] = array[low + i];
 for (int i = 0; i &lt; rightArray.length; i++)
 rightArray[i] = array[mid + i + 1];

 // Iterators containing current index of temp subarrays
 int leftIndex = 0;
 int rightIndex = 0;

 // Copying from leftArray and rightArray back into array
 for (int i = low; i &lt; high + 1; i++) {
 // If there are still uncopied elements in R and L, copy minimum of the two
 if (leftIndex &lt; leftArray.length &amp;&amp; rightIndex &lt; rightArray.length) {
 if (leftArray[leftIndex] &lt; rightArray[rightIndex]) {
 array[i] = leftArray[leftIndex];
 leftIndex++;
 } else {
 array[i] = rightArray[rightIndex];
 rightIndex++;
 }
 } else if (leftIndex &lt; leftArray.length) {
 // If all elements have been copied from rightArray, copy rest of leftArray
 array[i] = leftArray[leftIndex];
 leftIndex++;
 } else if (rightIndex &lt; rightArray.length) {
 // If all elements have been copied from leftArray, copy rest of rightArray
 array[i] = rightArray[rightIndex];
 rightIndex++;
 }
 }
}
</code></pre>
Running the following piece of code:
<pre><code class="hljs">int[] array = new int[]{5, 6, 7, 2, 4, 1, 7};
mergeSort(array, 0, array.length-1);
System.out.println(Arrays.toString(array));
</code></pre>
Will yield us a sorted array:
<pre><code class="hljs">[1, 2, 4, 5, 6, 7, 7]
</code></pre>
<h2 id="timecomplexity">Time Complexity</h2>
The average and worst-case time complexity of Merge Sort is O(nlogn), which is fair for a sorting algorithm. Here's how it performed after sorting an array containing 10,000 integers in random order:
<pre><code class="hljs">int[] array = new int[10000];
for (int i = 0; i &lt; array.length; i++) {
 array[i] = i;
}

// Shuffle array
Collections.shuffle(Arrays.asList(array));

// Print shuffled collection
for (int i = 0; i &lt; array.length; i++) {
 System.out.println(array[i]);
}

long startTime = System.nanoTime();
mergeSort(array, 0, array.lenth-1);
long endTime = System.nanoTime();

// Print sorted collection
for (int i = 0; i &lt; array.length; i++) {
 System.out.println(array[i]);
}

System.out.println();

// Print runtime in nanoseconds
System.out.println(&quot;Merge Sort runtime: &quot; + (endTime - startTime));
</code></pre>
And here are the results in seconds after running it 10 times:
<table class="table table-striped" style="white-space:nowrap; font-size:15px;">
 <tr>
 <th>time(s)</th>
 <th>Merge Sort</th>
 <th></th>
 </tr>
 <tr>
 <td>First Run</td>
 <td>0.00551</td>
 </tr>
 <tr>
 <td>Second Run</td>
 <td>0.00852</td>
 </tr>
 <tr>
 <td>Third Run</td>
 <td>0.00765</td>
 </tr>
 <tr>
 <td>Fourth Run</td>
 <td>0.00543</td>
 </tr>
 <tr>
 <td>Fifth Run</td>
 <td>0.00886</td>
 </tr>
 <tr>
 <td>Sixth Run</td>
 <td>0.00946</td>
 </tr>
 <tr>
 <td>Seventh Run</td>
 <td>0.00575</td>
 </tr>
 <tr>
 <td>Eight Run</td>
 <td>0.00765</td>
 </tr>
 <tr>
 <td>Ninth Run</td>
 <td>0.00677</td>
 </tr>
 <tr>
 <td>Tenth Run</td>
 <td>0.00550</td>
 </tr>
</table>
With an average run-time of 0.006s, it's pretty quick.
<h2 id="conclusion">Conclusion</h2>
Merge sort is a divide-and-conquer algorithm, which recursively calls itself on halved portions of the initial collection.
Another thing to note is that Merge Sort is an &quot;out-of-place&quot; sorting algorithm. This means that it does require extra space to store the elements its sorting, which can cause problems for memory-constrained systems. This is one trade-off of using this algorithm.
Although it's one of the quickest and most efficient sorting algorithms with the average time complexity of O(nlogn), right alongside Quicksort, Timsort, and Heapsort.me

David Landup

Merge Sort is a classic divide-and-conquer algorithm that recursively calls itself on halved portions of the initial collection. In this article, we'll implement Merge Sort in Java and compare it to Quicksort.

Merge Sort in Java

Muhammad Junaid Khalid

Using cURL in Python with PycURL

Quicksort is one of the most widespread sorting algorithm due to the relative simplicity of implementation and efficient performance. In this article, we'll implement Quicksort in Python.

Quicksort in Python

Robley Gori

AWS SQS allows us to decouple large systems by providing them with a loosely-coupled communication mechanism. In this article, we'll be using Node.js and AWS SQS to build a messaging system, ideal for microservices.

Message Queueing in Node.js with AWS SQS

Janith Kasun

Proxies have the ability to change the fundamental behavior of objects and functions.
In this article, we'll talk about JavaScript proxies, introduced in ES6 and showcase their functionality.

Introduction to JavaScript Proxies in ES6

Josh Simpson

There are many cloud-based hosting services online. In this article, we'll build a Node.js application, dockerize it and deploy it to a DigitalOcean Droplet to get it up and running online.