Merge Sort Work Area
Provide a work area for merge sort
Notes
The notion of a work area is fundamental to a merge sort.
As such, it is not an optimization.
The optimization is allocating the work area in the caller,
and recycling it in the actual merge sort algorithm.
The work area could have been allocated locally,
which would have been a performance bottleneck.
- Use work area
Segment Element
Parameter insertion
-
1454: sortlines (struct line *lines, int nlines, struct line *temp)
Segment Element
Code elision
Segment Element
Argument insertion
-
1472: sortlines (lo, nlo, temp);
Segment Element
Argument insertion
-
1475: sortlines (hi, nhi, temp);
Segment Element
Code elision
- Manage work area
Segment Element
Variable declaration
- 1560: struct line *tmp;
1561: int i, ntmp;
Segment Element
Code insertion
- 1570: ntmp = lines.alloc;
1571: tmp = (struct line *) xmalloc (ntmp * sizeof (struct line));
Segment Element
Code insertion
-
1579: if (lines.used > ntmp)
1580: {
1581: while (lines.used > ntmp)
1582: ntmp *= 2;
1583: tmp = (struct line *)
1584: xrealloc ((char *) tmp, ntmp * sizeof (struct line));
1585: }
Segment Element
Argument insertion
-
1586: sortlines (lines.lines, lines.used, tmp);
Segment Element
Code insertion
- 1609: free ((char *) tmp);