Added insertion sort as part of the sorting algorithms series e02 - Easy

MichaelVandi · MichaelVandi · commit 4cfa0339842a · 2020-08-05T18:17:23.000-04:00
diff --git a/Easy/08_05_2020_insertion_sort.java b/Easy/08_05_2020_insertion_sort.java
@@ -0,0 +1,29 @@
+/*
+    Time:
+        Best = O(n), Average = O(n^2), Worst = O(n^2)
+    Space: O(1)
+*/
+class Solution {
+    public int[] sortArray(int[] nums) {
+        // The very first number by itself is sorted
+        for (int i = 0; i < nums.length; i++) {
+            int j = i;
+            while (j > 0) {
+                // Insert nums j into its rightful position in the sorted array
+                if (nums[j] < nums[j - 1]) {
+                    // Swap them
+                    swap(nums, j, j - 1);
+                }
+                j--;
+            }
+            
+        }
+
+        return nums;
+    }
+    public void swap(int[] array, int i, int j) {
+        int temp = array[i];
+        array[i] = array[j];
+        array[j] = temp;
+    }
+}
