title: Trying to compare space complexities of 2 sorting algorithms. Don't know how to interpret the answer
body: <p>I have 2 sorting algorithms, merge sort and insertion sort. I am trying to examine how much ram memory they allocate during execution, to do a comparison. Both are sorting an array of  1000 elements, integers between 0-999.</p>
  
  <p>The programs are compiled to a binary called <code>main</code> (<code>merge_sort/main</code> and <code>insertion_sort/main</code>). So I am running:</p>
  
  <pre><code>memusage -T ./main
  </code></pre>
  
  <p>on both algorithms.</p>
  
  <p>both returns:</p>
  
  <pre><code>heap total: 73728, heap peak: 73728, stack peak: 6144
  </code></pre>
  
  <p>Why does they return the same? Shouldn't merge sort allocate more memory than insertion sort? Am I even using <code>memusage</code> correct?</p>
  
  <p>I have also tried to examine them using Valgrind, which also returns same for both:</p>
  
  <pre><code>==26544== HEAP SUMMARY:
  ==26544==     in use at exit: 0 bytes in 0 blocks
  ==26544==   total heap usage: 2 allocs, 2 frees, 73,728 bytes allocated
  </code></pre>
  
  <p>My theory is: that either I dont know what I am doing,</p>
  
  <p>or that the list that is sorted is to small. Therefore the memory usage looks the same.</p>
  
  <p>Code:</p>
  
  <p>Merge sort</p>
  
  <pre><code>/* C program for Merge Sort */
  #include&lt;stdlib.h&gt;
  #include&lt;stdio.h&gt;
  #include&lt;time.h&gt;
  
  // Merges two subarrays of arr[].
  // First subarray is arr[l..m]
  // Second subarray is arr[m+1..r]
  void merge(int arr[], int l, int m, int r)
  {
      int i, j, k;
      int n1 = m - l + 1;
      int n2 = r - m;
  
      /* create temp arrays */
      int L[n1], R[n2];
  
      /* Copy data to temp arrays L[] and R[] */
      for (i = 0; i &lt; n1; i++)
          L[i] = arr[l + i];
      for (j = 0; j &lt; n2; j++)
          R[j] = arr[m + 1+ j];
  
      /* Merge the temp arrays back into arr[l..r]*/
      i = 0; // Initial index of first subarray
      j = 0; // Initial index of second subarray
      k = l; // Initial index of merged subarray
      while (i &lt; n1 &amp;&amp; j &lt; n2)
      {
          if (L[i] &lt;= R[j])
          {
              arr[k] = L[i];
              i++;
          }
          else
          {
              arr[k] = R[j];
              j++;
          }
          k++;
      }
  
      /* Copy the remaining elements of L[], if there
      are any */
      while (i &lt; n1)
      {
          arr[k] = L[i];
          i++;
          k++;
      }
  
      /* Copy the remaining elements of R[], if there
      are any */
      while (j &lt; n2)
      {
          arr[k] = R[j];
          j++;
          k++;
      }
  }
  
  /* l is for left index and r is right index of the
  sub-array of arr to be sorted */
  void mergeSort(int arr[], int l, int r)
  {
      if (l &lt; r)
      {
          // Same as (l+r)/2, but avoids overflow for
          // large l and h
          int m = l+(r-l)/2;
  
          // Sort first and second halves
          mergeSort(arr, l, m);
          mergeSort(arr, m+1, r);
  
          merge(arr, l, m, r);
      }
  }
  
  /* UTILITY FUNCTIONS */
  /* Function to print an array */
  void printArray(int A[], int size)
  {
      int i;
      for (i=0; i &lt; size; i++)
          printf("%d ", A[i]);
      printf("\n");
  }
  
  /* Driver program to test above functions */
  int main()
  {
      int arr[] = {
          397, 326, 157, 581, 198, 158, 107, 479, 919, 288, 118, 14, 384, 389, 354, 905, 648, 24, 639, 279, 846, 896, 901, 491, 827, 502, 119, 520, 544, 688, 433, 542, 280, 834, 574, 739, 168, 714, 367, 547, 555, 616, 71, 583, 77, 372, 380, 414, 80, 828, 671, 900, 710, 852, 810, 471, 493, 832, 310, 579, 605, 174, 19, 576, 162, 695, 635, 851, 265, 48, 536, 228, 754, 300, 610, 272, 619, 825, 770, 147, 9, 813, 525, 135, 768, 654, 889, 446, 910, 678, 432, 172, 618, 41, 839, 589, 304, 484, 765, 357, 427, 617, 75, 683, 930, 593, 341, 149, 733, 27, 556, 474, 987, 156, 501, 665, 370, 523, 142, 420, 114, 798, 989, 382, 543, 879, 294, 305, 684, 331, 443, 383, 625, 647, 780, 811, 34, 621, 744, 842, 150, 938, 301, 495, 965, 392, 634, 358, 570, 789, 266, 242, 709, 278, 932, 57, 952, 475, 984, 136, 133, 637, 734, 207, 697, 362, 344, 332, 89, 529, 188, 164, 124, 317, 103, 257, 514, 364, 356, 203, 112, 831, 867, 644, 815, 452, 456, 260, 291, 90, 13, 21, 160, 217, 251, 459, 213, 110, 455, 56, 753, 127, 349, 884, 434, 982, 224, 410, 104, 540, 640, 973, 486, 945, 201, 166, 99, 535, 229, 725, 361, 483, 190, 743, 998, 409, 159, 102, 55, 219, 720, 33, 971, 859, 335, 887, 538, 363, 557, 696, 11, 951, 51, 845, 231, 723, 569, 63, 903, 185, 406, 505, 833, 309, 49, 599, 788, 511, 990, 196, 324, 803, 247, 970, 440, 504, 627, 205, 656, 308, 948, 690, 551, 819, 988, 608, 67, 519, 907, 510, 603, 256, 597, 880, 893, 214, 95, 270, 915, 179, 298, 378, 550, 953, 717, 321, 992, 863, 796, 868, 604, 152, 368, 15, 284, 17, 925, 808, 799, 841, 946, 974, 450, 546, 682, 91, 666, 402, 283, 736, 567, 679, 125, 299, 319, 762, 849, 785, 264, 797, 623, 401, 689, 140, 461, 171, 454, 624, 853, 724, 191, 130, 86, 451, 87, 109, 38, 61, 413, 348, 289, 829, 969, 670, 528, 588, 937, 766, 885, 237, 823, 592, 184, 73, 239, 643, 180, 10, 195, 277, 787, 431, 562, 390, 338, 146, 638, 85, 424, 652, 2, 631, 685, 405, 35, 387, 912, 333, 740, 692, 769, 66, 554, 565, 926, 223, 322, 826, 657, 858, 703, 1, 986, 312, 246, 31, 577, 323, 145, 439, 375, 39, 170, 106, 478, 978, 716, 254, 756, 37, 360, 350, 463, 269, 52, 64, 386, 509, 997, 429, 379, 655, 916, 878, 553, 794, 807, 197, 16, 840, 947, 860, 920, 963, 70, 183, 572, 763, 192, 729, 340, 238, 209, 469, 151, 167, 292, 303, 129, 847, 749, 4, 218, 216, 924, 215, 784, 243, 394, 836, 782, 476, 268, 78, 54, 590, 81, 908, 23, 704, 428, 778, 976, 680, 211, 622, 131, 273, 236, 487, 416, 767, 854, 870, 255, 837, 336, 611, 958, 233, 991, 3, 764, 83, 7, 541, 244, 792, 790, 0, 407, 418, 812, 334, 32, 872, 883, 537, 518, 72, 293, 886, 220, 866, 42, 730, 929, 891, 126, 470, 686, 329, 28, 568, 563, 659, 186, 706, 923, 497, 942, 844, 850, 492, 783, 715, 415, 153, 120, 448, 496, 468, 398, 620, 369, 373, 629, 79, 835, 711, 750, 311, 738, 346, 881, 121, 911, 50, 612, 498, 395, 955, 490, 774, 944, 506, 584, 664, 445, 173, 524, 561, 252, 713, 359, 771, 595, 96, 458, 956, 967, 422, 507, 177, 515, 342, 488, 759, 274, 275, 385, 816, 983, 306, 263, 830, 897, 760, 82, 426, 5, 698, 200, 981, 276, 559, 613, 154, 532, 735, 84, 345, 909, 94, 202, 302, 580, 508, 44, 134, 374, 898, 100, 993, 116, 712, 943, 646, 552, 975, 800, 6, 824, 328, 318, 960, 245, 708, 548, 403, 60, 931, 499, 676, 88, 894, 465, 921, 817, 693, 591, 957, 818, 721, 596, 649, 935, 261, 747, 391, 917, 314, 296, 460, 376, 412, 227, 240, 139, 871, 776, 691, 513, 93, 606, 531, 464, 694, 977, 108, 69, 259, 466, 417, 58, 737, 786, 43, 707, 933, 307, 74, 719, 653, 327, 746, 913, 262, 922, 731, 199, 494, 804, 877, 873, 732, 285, 727, 47, 210, 927, 914, 194, 758, 602, 582, 566, 941, 598, 809, 672, 966, 258, 137, 961, 902, 467, 92, 105, 316, 29, 234, 781, 675, 286, 226, 353, 857, 777, 472, 68, 985, 480, 330, 250, 248, 282, 962, 838, 176, 208, 40, 175, 178, 281, 396, 444, 436, 560, 521, 895, 366, 377, 586, 578, 212, 641, 232, 687, 571, 876, 585, 117, 101, 862, 701, 934, 939, 968, 189, 53, 677, 573, 869, 113, 642, 65, 607, 143, 979, 645, 856, 352, 20, 522, 249, 355, 148, 22, 473, 742, 98, 347, 419, 477, 705, 674, 757, 899, 430, 489, 425, 949, 726, 950, 123, 667, 399, 297, 594, 650, 587, 503, 141, 442, 748, 221, 775, 500, 339, 668, 400, 45, 814, 516, 663, 996, 772, 882, 230, 267, 722, 404, 821, 204, 755, 12, 702, 435, 822, 315, 630, 673, 848, 438, 482, 408, 928, 512, 371, 779, 626, 235, 527, 462, 904, 651, 661, 411, 752, 36, 980, 761, 485, 855, 241, 222, 287, 46, 802, 801, 206, 453, 111, 874, 295, 59, 628, 806, 290, 575, 600, 337, 728, 995, 138, 609, 875, 193, 30, 658, 558, 76, 481, 890, 745, 615, 132, 614, 795, 393, 351, 741, 564, 805, 457, 313, 545, 632, 964, 381, 25, 533, 26, 633, 62, 530, 751, 517, 936, 791, 820, 155, 940, 365, 843, 8, 918, 662, 225, 681, 388, 187, 660, 144, 793, 773, 181, 421, 161, 423, 447, 169, 994, 669, 700, 163, 526, 999, 959, 437, 449, 888, 271, 954, 18, 253, 320, 892, 864, 718, 865, 601, 699, 972, 549, 115, 441, 128, 861, 539, 165, 534, 325, 636, 122, 97, 182, 906, 343
      };
      int n = sizeof(arr)/sizeof(arr[0]);
  
      clock_t begin = clock();
  
      /* here, do your time-consuming job */
      mergeSort(arr, 0, n-1);
  
      clock_t end = clock();
      double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
  
      printf("Merge: %.10f", time_spent);
      printf("\n");
      return 0;
  }
  </code></pre>
  
  <p>Insertion sort</p>
  
  <pre><code>// C program for insertion sort
  #include &lt;math.h&gt;
  #include &lt;stdio.h&gt;
  #include &lt;time.h&gt;
  #include &lt;unistd.h&gt;
  
  /* Function to sort an array using insertion sort*/
  void insertionSort(int arr[], int n)
  {
      int i, key, j;
      for (i = 1; i &lt; n; i++) {
          key = arr[i];
          j = i - 1;
  
          /* Move elements of arr[0..i-1], that are
          greater than key, to one position ahead
          of their current position */
          while (j &gt;= 0 &amp;&amp; arr[j] &gt; key) {
              arr[j + 1] = arr[j];
              j = j - 1;
          }
          arr[j + 1] = key;
      }
  }
  
  // A utility function to print an array of size n
  void printArray(int arr[], int n)
  {
      int i;
      for (i = 0; i &lt; n; i++)
          printf("%d ", arr[i]);
      printf("\n");
  }
  
  /* Driver program to test insertion sort */
  int main()
  {
      int arr[] = {
          397, 326, 157, 581, 198, 158, 107, 479, 919, 288, 118, 14, 384, 389, 354, 905, 648, 24, 639, 279, 846, 896, 901, 491, 827, 502, 119, 520, 544, 688, 433, 542, 280, 834, 574, 739, 168, 714, 367, 547, 555, 616, 71, 583, 77, 372, 380, 414, 80, 828, 671, 900, 710, 852, 810, 471, 493, 832, 310, 579, 605, 174, 19, 576, 162, 695, 635, 851, 265, 48, 536, 228, 754, 300, 610, 272, 619, 825, 770, 147, 9, 813, 525, 135, 768, 654, 889, 446, 910, 678, 432, 172, 618, 41, 839, 589, 304, 484, 765, 357, 427, 617, 75, 683, 930, 593, 341, 149, 733, 27, 556, 474, 987, 156, 501, 665, 370, 523, 142, 420, 114, 798, 989, 382, 543, 879, 294, 305, 684, 331, 443, 383, 625, 647, 780, 811, 34, 621, 744, 842, 150, 938, 301, 495, 965, 392, 634, 358, 570, 789, 266, 242, 709, 278, 932, 57, 952, 475, 984, 136, 133, 637, 734, 207, 697, 362, 344, 332, 89, 529, 188, 164, 124, 317, 103, 257, 514, 364, 356, 203, 112, 831, 867, 644, 815, 452, 456, 260, 291, 90, 13, 21, 160, 217, 251, 459, 213, 110, 455, 56, 753, 127, 349, 884, 434, 982, 224, 410, 104, 540, 640, 973, 486, 945, 201, 166, 99, 535, 229, 725, 361, 483, 190, 743, 998, 409, 159, 102, 55, 219, 720, 33, 971, 859, 335, 887, 538, 363, 557, 696, 11, 951, 51, 845, 231, 723, 569, 63, 903, 185, 406, 505, 833, 309, 49, 599, 788, 511, 990, 196, 324, 803, 247, 970, 440, 504, 627, 205, 656, 308, 948, 690, 551, 819, 988, 608, 67, 519, 907, 510, 603, 256, 597, 880, 893, 214, 95, 270, 915, 179, 298, 378, 550, 953, 717, 321, 992, 863, 796, 868, 604, 152, 368, 15, 284, 17, 925, 808, 799, 841, 946, 974, 450, 546, 682, 91, 666, 402, 283, 736, 567, 679, 125, 299, 319, 762, 849, 785, 264, 797, 623, 401, 689, 140, 461, 171, 454, 624, 853, 724, 191, 130, 86, 451, 87, 109, 38, 61, 413, 348, 289, 829, 969, 670, 528, 588, 937, 766, 885, 237, 823, 592, 184, 73, 239, 643, 180, 10, 195, 277, 787, 431, 562, 390, 338, 146, 638, 85, 424, 652, 2, 631, 685, 405, 35, 387, 912, 333, 740, 692, 769, 66, 554, 565, 926, 223, 322, 826, 657, 858, 703, 1, 986, 312, 246, 31, 577, 323, 145, 439, 375, 39, 170, 106, 478, 978, 716, 254, 756, 37, 360, 350, 463, 269, 52, 64, 386, 509, 997, 429, 379, 655, 916, 878, 553, 794, 807, 197, 16, 840, 947, 860, 920, 963, 70, 183, 572, 763, 192, 729, 340, 238, 209, 469, 151, 167, 292, 303, 129, 847, 749, 4, 218, 216, 924, 215, 784, 243, 394, 836, 782, 476, 268, 78, 54, 590, 81, 908, 23, 704, 428, 778, 976, 680, 211, 622, 131, 273, 236, 487, 416, 767, 854, 870, 255, 837, 336, 611, 958, 233, 991, 3, 764, 83, 7, 541, 244, 792, 790, 0, 407, 418, 812, 334, 32, 872, 883, 537, 518, 72, 293, 886, 220, 866, 42, 730, 929, 891, 126, 470, 686, 329, 28, 568, 563, 659, 186, 706, 923, 497, 942, 844, 850, 492, 783, 715, 415, 153, 120, 448, 496, 468, 398, 620, 369, 373, 629, 79, 835, 711, 750, 311, 738, 346, 881, 121, 911, 50, 612, 498, 395, 955, 490, 774, 944, 506, 584, 664, 445, 173, 524, 561, 252, 713, 359, 771, 595, 96, 458, 956, 967, 422, 507, 177, 515, 342, 488, 759, 274, 275, 385, 816, 983, 306, 263, 830, 897, 760, 82, 426, 5, 698, 200, 981, 276, 559, 613, 154, 532, 735, 84, 345, 909, 94, 202, 302, 580, 508, 44, 134, 374, 898, 100, 993, 116, 712, 943, 646, 552, 975, 800, 6, 824, 328, 318, 960, 245, 708, 548, 403, 60, 931, 499, 676, 88, 894, 465, 921, 817, 693, 591, 957, 818, 721, 596, 649, 935, 261, 747, 391, 917, 314, 296, 460, 376, 412, 227, 240, 139, 871, 776, 691, 513, 93, 606, 531, 464, 694, 977, 108, 69, 259, 466, 417, 58, 737, 786, 43, 707, 933, 307, 74, 719, 653, 327, 746, 913, 262, 922, 731, 199, 494, 804, 877, 873, 732, 285, 727, 47, 210, 927, 914, 194, 758, 602, 582, 566, 941, 598, 809, 672, 966, 258, 137, 961, 902, 467, 92, 105, 316, 29, 234, 781, 675, 286, 226, 353, 857, 777, 472, 68, 985, 480, 330, 250, 248, 282, 962, 838, 176, 208, 40, 175, 178, 281, 396, 444, 436, 560, 521, 895, 366, 377, 586, 578, 212, 641, 232, 687, 571, 876, 585, 117, 101, 862, 701, 934, 939, 968, 189, 53, 677, 573, 869, 113, 642, 65, 607, 143, 979, 645, 856, 352, 20, 522, 249, 355, 148, 22, 473, 742, 98, 347, 419, 477, 705, 674, 757, 899, 430, 489, 425, 949, 726, 950, 123, 667, 399, 297, 594, 650, 587, 503, 141, 442, 748, 221, 775, 500, 339, 668, 400, 45, 814, 516, 663, 996, 772, 882, 230, 267, 722, 404, 821, 204, 755, 12, 702, 435, 822, 315, 630, 673, 848, 438, 482, 408, 928, 512, 371, 779, 626, 235, 527, 462, 904, 651, 661, 411, 752, 36, 980, 761, 485, 855, 241, 222, 287, 46, 802, 801, 206, 453, 111, 874, 295, 59, 628, 806, 290, 575, 600, 337, 728, 995, 138, 609, 875, 193, 30, 658, 558, 76, 481, 890, 745, 615, 132, 614, 795, 393, 351, 741, 564, 805, 457, 313, 545, 632, 964, 381, 25, 533, 26, 633, 62, 530, 751, 517, 936, 791, 820, 155, 940, 365, 843, 8, 918, 662, 225, 681, 388, 187, 660, 144, 793, 773, 181, 421, 161, 423, 447, 169, 994, 669, 700, 163, 526, 999, 959, 437, 449, 888, 271, 954, 18, 253, 320, 892, 864, 718, 865, 601, 699, 972, 549, 115, 441, 128, 861, 539, 165, 534, 325, 636, 122, 97, 182, 906, 343,
      };
  
      int n = sizeof(arr)/sizeof(arr[0]);
  
      //printf("n: %d", n);
      //printf("Unsorted array: ");
      //printArray(arr, n);
      //printf("\n");
      clock_t begin = clock();
  
      /* here, do your time-consuming job */
      insertionSort(arr, n);
  
      clock_t end = clock();
      double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
  
      //printf("Sorted array: ");
      //printArray(arr, n);
      //printf("\n");
  
      printf("Inser: %.10f", time_spent);
      printf("\n");
  
  
  
      return 0;
  }
  </code></pre>